BFS(Java)

• 通过队列进行广度遍历,然后保存坐标和父节点

DFS(Java)

• 递归 + 回溯

import java.util.*;
class Node{
    public int x,y,step;
    Node fa;
    Node(){}
    Node(int x,int y,int step){
        this.x = x;
        this.y = y;
        this.step = step;
    }
    Node(int x,int y,int step,Node fa){
        this.x = x;
        this.y = y;
        this.step = step;
        this.fa = fa;
    }
}
public class Main{
    public static void bfs(int [][]vis, int [][]graph,int n, int m){
        int [][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
        LinkedList<Node> q = new LinkedList<>();
        Node niu = new Node();
        q.offer(new Node(0,0,0,null));
        vis[0][0] = 1;
        while(!q.isEmpty()){
            Node node = q.poll();
            for(int i = 0;i<4;i++){
                int x = node.x + dir[i][0];
                int y = node.y + dir[i][1];
                if(x<n && x>=0 && y < m && y>=0 && graph[x][y]==0 && vis[x][y]==0){
                    vis[x][y] = 1;
                    q.offer(new Node(x,y,node.step+1,node));
                    if(x==n-1&&y==m-1) niu = new Node(x,y,node.step+1,node);
                }                  
            }
        }
        List<int[]> list = new ArrayList<>();
        while(niu!=null){
            int [] t = new int[2];
            t[0] = niu.x;
            t[1] = niu.y;
            list.add(t);
            niu = niu.fa;
        }
        Collections.reverse(list);
        for(int i=0;i<list.size();i++) System.out.println("("+list.get(i)[0]+","+list.get(i)[1]+")");
        
    }
    static int min = Integer.MAX_VALUE;
    static Node st;
    
    public static void dfs(int x,int y, int step,int [][] graph, int [][] vis, Node fa){
        int n = graph.length;
        int m = graph[0].length;
        if(x==n-1 && y==m-1) {
            if(min>step){
                min = step;
                st = new Node(x,y,step,fa);
            }
            return ;
        }
        int [][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
        for(int i = 0;i<4;i++){
            vis[x][y] = 1;
            int xx = x + dir[i][0];
            int yy = y + dir[i][1];
            if(xx<n && xx>=0 && yy < m && yy>=0 && graph[xx][yy]==0 && vis[xx][yy]==0){
                dfs(xx, yy, step+1, graph, vis, new Node(x,y,step,fa));
            }
            vis[x][y] = 0;  
        }
    }
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int [][] graph = new int [n][m];
        int [][] vis = new int[n][m];
        for(int i = 0 ;i<n;i++){
            for(int j = 0;j<m;j++){
                graph[i][j] = sc.nextInt();
            }
        }
//         bfs(vis, graph,n,m); // 广度优先
        dfs(0, 0, 0, graph, vis, null); // 深度优先
//         System.out.println(min);
        List<int[]> list = new ArrayList<>();
        while(st!=null){
            int [] t = new int[2];
            t[0] = st.x;
            t[1] = st.y;
            list.add(t);
            st = st.fa;
        }
        Collections.reverse(list);
        for(int i=0;i<list.size();i++) System.out.println("("+list.get(i)[0]+","+list.get(i)[1]+")");
        
        
    }
}