题解 | #迷宫问题# 【DFS】

DFS

思路

1. dfs 方法参数：dfs(int[][] maze, List<int[]> path, int x, int y)
2. 终止条件（先污染，后治理 写法）
   • 若当前位置 (x, y) 超出迷宫范围、或者当前位置是 ，则结束
   • 若当前位置 (x, y) 为终点（右下角），则收集路径，并结束
3. DFS 搜索逻辑：搜索当前点相邻位置的上、下、左、右四个方向

import java.util.*;

public class Main {
    private static int n;
    private static int m;
    private static List<int[]> res = new ArrayList<>();
    private static final int[] dirx = {-1, 1, 0, 0};
    private static final int[] diry = {0, 0, -1, 1};    

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 输入
        n = in.nextInt();
        m = in.nextInt();
        int[][] maze = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                maze[i][j] = in.nextInt();
            }
        }

        dfs(maze, new ArrayList<int[]>(), 0, 0);
        for (int[] p : res) {
            System.out.println("(" + p[0] + "," + p[1] + ")");
        }
        // System.out.println(res.size());
        in.close();
    }

    private static void dfs(int[][] maze, List<int[]> path, int x, int y) {
        // 终止条件（先污染，后治理 写法）
        if (!isValid(x, y) || maze[x][y] == 1) {
            return;
        }
        if (x == n - 1 && y == m - 1) {
            if (res.size() == 0 || path.size() < res.size()) {
                path.add(new int[] {n - 1, m - 1}); // 终点
                res = new ArrayList<>(path);
            }
            return;
        }
        // 搜索上、下、左、右四个方向
        for (int i = 0; i < 4; i++) {
            maze[x][y] = 1;
            path.add(new int[] {x, y});
            dfs(maze, path, x + dirx[i], y + diry[i]);
            maze[x][y] = 0; // 回溯
            path.remove(path.size() - 1);
        }
    }

    // 判断 (x, y) 是否在迷宫区域内
    static boolean isValid(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }
}

BFS