题解 | #迷宫问题#

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            // 获取输入的矩阵内容
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int[][] map = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    map[i][j] = scanner.nextInt();
                }
            }
            List<Pos> list = new ArrayList<>();
            // 回溯计算路径
            dfs(map, list, 0, 0);
            // 输出路径点坐标
            for (Pos pos : list) {
                System.out.println("(" + pos.x + "," + pos.y + ")");
            }
        }
    }

    /**
     * 从(0,0)开始,向后遍历搜索正确路径输出:相邻路径可以走则添加入path,否则回溯并取出
     *
     * @param map  输入的坐标
     * @param path 输出的list集合
     * @param x    当前坐标x
     * @param y    当前坐标y
     * @return
     */
    static boolean dfs(int[][] map, List<Pos> path, int x, int y) {
        // 添加路径并标记已走:起始点为(0,0),
        path.add(new Pos(x, y));
        map[x][y] = 1;

        // 路径走完,结束标记
        if (x == map.length - 1 && y == map[0].length - 1) {
            return true;
        }

        // 路径遍历
        if (x - 1 >= 0 && map[x - 1][y] == 0) {
            if (dfs(map, path, x - 1, y)) {
                return true;
            }
        }
        if (x + 1 < map.length && map[x + 1][y] == 0) {
            if (dfs(map, path, x + 1, y)) {
                return true;
            }
        }
        if (y - 1 >= 0 && map[x][y - 1] == 0) {
            if (dfs(map, path, x, y - 1)) {
                return true;
            }
        }
        if (y + 1 < map[0].length && map[x][y + 1] == 0) {
            if (dfs(map, path, x, y + 1)) {
                return true;
            }
        }
        // 相邻路径走不通,回溯
        path.remove(path.size() - 1);
        map[x][y] = 0;
        return false;
    }

    static class Pos {
        int x;
        int y;

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