2024-01-19

1.排列数字，深度遍历

import java.util.Scanner;

public class Main{
    static int n, N = 10;
    static int[] path = new int[N];
    static boolean[] st = new boolean[N];//用来标志数字有没有被排列过
    
    public static void dfs(int u, int n){
        //因为这个n不能在全局搞进去，所以要弄成一个参数放进来
        if(u == n){
            for(int i = 0; i < n; i ++){
                System.out.print(path[i] + " ");//这里是第几层的意思
            }
            System.out.println();
            return;
        }
        for(int i = 1; i <= n; i ++){
            if(!st[i]){
                path[u] = i;//这里是要排列的数字
                st[i] = true;
                dfs(u + 1, n);//由于这里传进去的是u+1，所以到临界点时u==n用来判断，但是还是最多只有n-1层
                st[i] = false;//清理现场（看递归函数在什么位置）递归结束之后，紧接着就恢复现场
            }
        }
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(0, n);//从第0层开始
    }
}

2.n皇后问题
第一种按行遍历

import java.util.Scanner;

public class Main{
    static int N = 20, n;//因为对角线的个数是2n-1
    static char[][] path = new char[N][N];
    static boolean[] col = new boolean[N], dg = new boolean[N], udg = new boolean[N]; 
    
    public static void dfs(int u){
        if(u == n){
            for(int i = 0; i < n; i ++){
                for(int j = 0; j < n; j ++){
                    System.out.print(path[i][j]);
                }
                System.out.println();
            }
            System.out.println();
            return;
        }
        for(int i = 0; i < n; i ++)//这里的i是列数，当前枚举的是第u行
        {
            if(!col[i] && !dg[u + i] && !udg[n - u + i]){
                path[u][i] = 'Q';
                col[i] = dg[u + i] = udg[n - u + i] = true;
                dfs(u + 1);
                col[i] = dg[u + i] = udg[n - u + i] = false;
                path[u][i] = '.';//要在这里加上这一串！！！
            }
        }
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < n; j ++){
                path[i][j] = '.';
            }
        }
        dfs(0);
    }
}

第二种方法

import java.util.Scanner;

public class Main{
    static int N = 20, n;//因为对角线的个数是2n-1
    static char[][] path = new char[N][N];
    static boolean[] col = new boolean[N], dg = new boolean[N], udg = new boolean[N];
    static boolean[] row = new boolean[N];
    
    public static void dfs(int x, int y, int s)//当前的横坐标x，纵坐标y，s已经放置了的皇后的数量
    {
        if(y == n){
            y = 0;
            x ++;
        }
        if(x == n){
            if(s == n){
                for(int i = 0; i < n; i ++){
                    for(int j = 0; j < n; j ++){
                        System.out.print(path[i][j]);
                    }
                    System.out.println();
                }
                System.out.println();
            }
            return;
        }
        
        //不放皇后
        dfs(x, y + 1,s);
        
        //放皇后
        if(!row[x] && !col[y] && !dg[x + y] && !udg[n - x + y]){
            path[x][y] = 'Q';
            row[x] = col[y] = dg[x + y] = udg[n - x + y] = true;
            dfs(x, y + 1,s + 1);
            row[x] = col[y] = dg[x + y] = udg[n - x + y] = false;
            path[x][y] = '.';//要在这里加上这一串！！！
        }
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < n; j ++){
                path[i][j] = '.';
            }
        }
        dfs(0, 0, 0);
    }
}

4.数字迷宫 只有0可以走，从左上走到右下

import java.io.*;
import java.util.*;


class Node{
    int x;
    int y;
        
    public Node(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main{    
    static int N = 110, n, m;
    static int[][] a = new int[N][N];
    static int[][] d = new int[N][N];
    
    public static int bfs(){
        Queue<Node> q = new LinkedList();
        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};
        q.offer(new Node(0, 0));
        
        while(!q.isEmpty()){
            Node head = q.poll();
            
            for(int i = 0; i < 4; i ++){
                int x = head.x + dx[i];
                int y = head.y + dy[i];
                
                if(x >= 0 && y >= 0 && x < n && y < m && d[x][y] == 0 && a[x][y] == 0){
                    q.offer(new Node(x,y));
                    d[x][y] = d[head.x][head.y] + 1;
                }
            }
        }
        return d[n - 1][m - 1];
    }
    
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        for(int i = 0; i < n; i ++){
            String[] st = br.readLine().split(" ");
            for(int j = 0; j < m; j ++){
                a[i][j] = Integer.parseInt(st[j]);
                d[i][j] = 0;
            }
        }
        System.out.print(bfs());
        bw.flush();
    }
}