题解 | 迷宫问题 DFS解法和BFS解法

DFS：需要额外维护一个path数组来存储路径，以及使用flag来判断是否已经到达终点

import java.util.*;

public class Main {
    private static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static int[][] grid;
    private static int h, w;
    private static boolean[][] visited;
    private static List<int[]> path;
    private static boolean flag;

    private static void dfs(int x, int y) {
        if(x == h - 1 && y == w - 1) {
            flag = true;
            return;
        }

        for(int i = 0; i < 4; i++) {
            int nxt_x = x + dir[i][0];
            int nxt_y = y + dir[i][1];
            if(nxt_x >= 0 && nxt_x < h && nxt_y >= 0 && nxt_y < w && grid[nxt_x][nxt_y] == 0 && !visited[nxt_x][nxt_y]) {
                visited[nxt_x][nxt_y] = true;
                path.add(new int[] {nxt_x, nxt_y});
                dfs(nxt_x, nxt_y);
                if(flag) {
                    break;
                }
                visited[nxt_x][nxt_y] = false;
                path.remove(path.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        h = in.nextInt();
        w = in.nextInt();
        grid = new int[h][w];
        path = new ArrayList<>();
        visited = new boolean[h][w];
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                grid[i][j] = in.nextInt();
            }
        }
        visited[0][0] = true;
        path.add(new int[] {0, 0});
        dfs(0, 0);
        for(int[] point : path) {
            System.out.println("(" + point[0] + "," + point[1] + ")");
        }
    }
}

BFS：定义一个Node类，存储当前坐标以及路径

import java.util.*;

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

public class Main {
    private static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static int[][] grid;
    private static int h, w;
    private static boolean[][] visited;

    private static List<int[]> bfs() {
        Queue<Node> q = new ArrayDeque<>();
        q.offer(new Node(0, 0, null));
        visited[0][0] = true;

        while (!q.isEmpty()) {
            Node cur = q.poll();
            int x = cur.x, y = cur.y;
            
            // 到达终点，回溯路径
            if(x == h - 1 && y == w - 1) {
                List<int[]> path = new ArrayList<>();
                while(cur != null) {
                    path.add(new int[] {cur.x, cur.y});
                    cur = cur.father;
                }
                // 反转回溯得到的路径
                Collections.reverse(path);
                return path;
            }

            for (int i = 0; i < 4; i++) {
                int nxt_x = x + dir[i][0];
                int nxt_y = y + dir[i][1];
                if (nxt_x >= 0 && nxt_x < h && nxt_y >= 0 && nxt_y < w &&
                        grid[nxt_x][nxt_y] == 0 && !visited[nxt_x][nxt_y]) {
                    visited[nxt_x][nxt_y] = true;
                    q.offer(new Node(nxt_x, nxt_y, cur));
                }
            }
        }

        return null;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        h = in.nextInt();
        w = in.nextInt();
        grid = new int[h][w];
        visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                grid[i][j] = in.nextInt();
            }
        }
        List<int[]> ans = bfs();
        for (int[] point : ans) {
            System.out.println("(" + point[0] + "," + point[1] + ")");
        }
    }
}