题解 | #迷宫问题#

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
class Node1{
    int x;
    int y;
    public Node1(int x,int y){
        this.x=x;
        this.y=y;
    }
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        String str;
        while ((str=reader.readLine())!=null){
            String[] arr=str.split(" ");
            int row=Integer.parseInt(arr[0]);
            int col=Integer.parseInt(arr[1]);
            int[][] mat=new int[row][col];
            for (int i = 0; i < row; i++) {
                str=reader.readLine();
                arr=str.split(" ");
                for (int j = 0; j < col; j++) {
                    mat[i][j]=Integer.parseInt(arr[j]);
                }
            }
            ArrayList<Node1> path=new ArrayList<>();
            ArrayList<Node1> minpath=new ArrayList<>();
            int[][] book=new int[row][col];
            getMinPath(mat,row,col,0,0,book,path,minpath);

            for (Node1 n:minpath) {
                System.out.println("("+n.x+","+n.y+")");
            }
        }
    }
    public static void getMinPath(int[][] mat,int row,int col,int x,int y,int[][] book,ArrayList<Node1> path,ArrayList<Node1> minpaht){
        if(x<0||x>=row||y<0||y>=col||book[x][y]==1||mat[x][y]==1){
            return;
        }
        path.add(new Node1(x,y));
        book[x][y]=1;
        if(x==row-1&&y==col-1){
            if(minpaht.isEmpty()||path.size()<minpaht.size()){
                minpaht.clear();
                for (Node1 n:path) {
                    minpaht.add(n);
                }
            }
        }
        getMinPath(mat,row,col,x+1,y,book,path,minpaht);
        getMinPath(mat,row,col,x-1,y,book,path,minpaht);
        getMinPath(mat,row,col,x,y+1,book,path,minpaht);
        getMinPath(mat,row,col,x,y-1,book,path,minpaht);
        path.remove(path.size()-1);
        book[x][y]=0;
    }
}