题解 | #迷宫问题#

import java.util.Scanner;

import java.util.*;
// 题目已经提示了 【迷宫只有一条通道】，则直接使用 DFS 找路径就行了，如不有多条路径找最短考虑使用 BFS
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            List<MazePos> posList = new ArrayList<>();
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int map[][] = new int[x][y];
            for (int i = 0; i < x; i++) {
                for (int j = 0; j < y; j++) {
                    map[i][j] = scanner.nextInt();
                }
            }

            findSolve(map, 0, 0, posList);
            for (MazePos mazePos : posList) {
                System.out.println("(" + mazePos.x + "," + mazePos.y + ")");
            }
        }




    }

    private static boolean findSolve(int map[][], int x, int y,
                                     List<MazePos> posList) {
        // 放入集合
        posList.add(new MazePos(x, y));
        // 设置为已经走过
        map[x][y] = 1;

        // 设定成功条件
        if (map.length - 1 == x && map[0].length - 1 == y) {
            return true;
        }

        // 右走
        if (map.length - 1 > x && map[x + 1][y] == 0) {
            if (findSolve(map, x + 1, y, posList)) {
                return true;
            }
        }

        // 左走
        if (x - 1 > -1 && map[x - 1][y] == 0) {
            if (findSolve(map, x - 1, y, posList)) {
                return true;
            }
        }

        // 下走
        if (map[0].length - 1 > y && map[x][y + 1] == 0) {
            if (findSolve(map, x, y + 1, posList)) {
                return true;
            }
        }

        // 上走
        if (y - 1 > -1 && map[x][y - 1] == 0) {
            if (findSolve(map, x, y - 1, posList)) {
                return true;
            }
        }

        posList.remove(posList.size() - 1);
        map[x][y] = 0;
        return false;
    }


}

class MazePos {
    int x;
    int y;

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