题解 | 迷宫问题

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<String> road = new ArrayList<>();
    public static boolean dfs(int x, int y, int[][] a){
        if(x == a.length - 1 && y == a[0].length - 1){
            road.add("(" + x + "," + y + ")");
            return true;
        }
        if(x < 0 || y < 0 || x > a.length - 1 || y > a[0].length - 1)
            return false;
        if(a[x][y] == 1)
            return false;

        a[x][y] = 1;
        road.add("(" + x + "," + y + ")");
        boolean res = dfs(x - 1, y, a)
                || dfs(x + 1, y, a)
                || dfs(x, y - 1, a)
                || dfs(x, y + 1, a);
        a[x][y] = 0;
        if (!res)
            road.remove(road.size() - 1);
        return res;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int h = in.nextInt();
        int w = in.nextInt();
        int[][] a = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                a[i][j] = in.nextInt();
            }
        }
        dfs(0, 0, a);
        road.forEach(e ->{
            System.out.println(e);
        });
    }
}

这段代码使用 深度优先搜索（DFS） 在二维矩阵（迷宫）中寻找从起点 (0, 0) 到终点 (右下角) 的路径。以下是核心思路的总结：

1. 终止条件

• 到达终点：当坐标 (x, y) 等于矩阵右下角 (a.length-1, a[0].length-1) 时，记录路径并返回 true。java复制
• 越界或障碍物：如果坐标越界或当前格子是障碍物（a[x][y] == 1），直接返回 false。java复制

2. 递归搜索

• 标记访问：将当前格子标记为已访问（a[x][y] = 1），并加入路径列表 road。java复制
• 四方向探索：依次尝试向 上、下、左、右 四个方向递归搜索，通过短路或（||）确保找到一条可行路径后立即终止其他方向的搜索。java复制
• 回溯处理：如果当前路径 不可行（res == false），移除当前格子从路径列表 road 中。恢复现场：将当前格子重置为未访问（a[x][y] = 0），允许其他路径探索。java复制

3. 输入与输出

• 输入：读取矩阵的行数 h、列数 w 和矩阵数据（0 表示可通行，1 表示障碍物）。java复制
• 输出：打印从起点到终点的路径坐标（格式为 (x,y)）。java复制

关键点

1. 回溯法：通过标记/取消标记避免重复访问，确保路径唯一性。
2. 短路优化：|| 运算符在找到路径后立即终止后续递归，提升效率。
3. 路径记录：使用 ArrayList<String> 动态维护当前路径，回溯时需同步更新。