题解 | #迷宫问题#

import java.util.*;
public class Main {
        private static Stack<int[]> path;
        private static ArrayList<int[]> minpath;
        private static int[][] matrix;
        private static boolean[][] visited;
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            while(sc.hasNext()){
                String[] str = sc.nextLine().split(" ");//第一行 接收几行几列
                int rows = Integer.parseInt(str[0]);//行数
                int cols = Integer.parseInt(str[1]);//列数
                path = new Stack<>();
                minpath = null; //最短路径
                matrix = new int[rows][cols];//二维矩阵
                visited = new boolean[rows][cols];//访问过的点置为true
                //根据前面的行数,开始遍历每一行 存入到二维数组中
                for(int i=0;i<rows;i++){
                    String[] str1= sc.nextLine().split(" ");
                    for(int j =0;j<cols;j++){
                        matrix[i][j] = Integer.parseInt(str1[j]); //01 02 03...
                    }
                }
                //因为需要一遍遍去走 哪个是最短路径 所以有递归方法
                dfs(0,0);//从起点开始 
                //递归结束后 拼装最短路径的结果
                StringBuffer sb = new StringBuffer();
                for(int[] result : minpath){
                    sb.append('(').append(result[0]).append(',').append(result[1]).append(")\n");
                }
                System.out.print(sb.toString());
            }
        }
        private static void dfs(int i,int j){
            //设置递归条件,当走过终点了 或者碰到墙了(行 列分开统计) 不走了 当走过了 不走了 走到终点 也不走了 
            //并且一定要有最短路径 
            if(i>matrix.length-1 || i<0 
               || j>matrix[0].length-1 || j<0 
               || visited[i][j] 
               || matrix[i][j]==1 
               || (minpath!=null && path.size()>=minpath.size())){
                return;
            }
            
            //当走到终点的时候 把此时的(坐标)传给path  就结束不走了
            if(i==matrix.length-1 && j==matrix[0].length-1){
                path.add(new int[]{i,j});
                minpath = new ArrayList<>(path);
                path.pop();//把栈顶弹出
                return;
            }
            
            //正常走的情况
            path.add(new int[]{i,j});
            visited[i][j]=true;//标记走过的点
            
            //往四个方向 上下左右遍历走
            dfs(i+1, j);
            dfs(i, j+1);
            dfs(i-1, j);
            dfs(i, j-1);
            
            visited[i][j]=false;//清除这一次标记
            path.pop();
        } 
}