题解 | #迷宫问题#

import java.io.IOException;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int[][] maze = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                maze[i][j] = scanner.nextInt();
            }
        }

        maze[0][0] = 1;
        List<int[]> curPath = new ArrayList<>();
        curPath.add(new int[]{0, 0});
        dfs(maze, curPath, 0, 0);

        for (int[] step : minPath) {
            System.out.println("(" + step[0] + "," + step[1] + ")");
        }
    }


    static List<int[]> minPath = null;
    static int[][] steps = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    static void dfs(int[][] maze, List<int[]> curPath, int curI, int curJ) {
        if (curI == maze.length - 1 && curJ == maze[0].length - 1) {
            if (minPath == null || minPath.size() > curPath.size()) {
                minPath = new ArrayList<>(curPath);
            }
            return;
        }
        for (int[] nextStep : steps) {
            int nextI = curI + nextStep[0];
            int nextJ = curJ + nextStep[1];
            if (nextI >= 0 && nextJ >= 0
                    && nextI < maze.length && nextJ < maze[0].length
                    && maze[nextI][nextJ] != 1) {
                maze[nextI][nextJ] = 1;
                curPath.add(new int[]{nextI, nextJ});
                dfs(maze, curPath, nextI, nextJ);
                curPath.remove(curPath.size() - 1);
                maze[nextI][nextJ] = 0;
            }
        }
    }
}