题解 | #迷宫问题#回溯法解迷宫，找到最短的路径，详见注释（欢迎批评指正）

import java.util.*;

public class Main {
    public static ArrayList<int[]> path = new ArrayList<>();//搜索所有可能的路径
    public static ArrayList<int[]> best_path = new ArrayList<>();//最短路径
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            path.clear();
            best_path.clear();//每个用例之前，都要清空下路径
            int n = in.nextInt();
            int 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(0,0,maze);//深搜+回溯
            for(int[] pathi:best_path){
                System.out.println("(" + pathi[0] + "," + pathi[1] + ")");
            }
        }
    }
    public static void dfs(int i,int j,int[][] maze){
        //越界了
        if(i<0 || i>maze.length-1 || j<0 || j>maze[0].length-1){
            return;
        }
        //撞墙了
        if(maze[i][j]==1){
            return;
        }
        //终止条件,找到终点了
        if(i==maze.length-1 && j==maze[0].length-1){
            path.add(new int[]{maze.length-1,maze[0].length-1});//添加终点
            if(best_path.size()==0 || path.size()<best_path.size()){//遇到更短的路径
                best_path.clear();//清空之前的路径
                for(int[] path0:path){
                    best_path.add(path0);
                }
            }
            return;
        }
        maze[i][j] = 1;//标记走过的点
        path.add(new int[]{i,j});//添加到路径中
        dfs(i-1,j,maze);
        dfs(i+1,j,maze);
        dfs(i,j-1,maze);
        dfs(i,j+1,maze);//以i j为中心，上下左右搜索
        maze[i][j] = 0;//回溯，恢复到之前的状态
        path.remove(path.size()-1);//回溯，移除最后一个点
    }
}