题解 | #迷宫问题#

static要clear

import java.util.*;

public class Main{
    public static List pathx=new ArrayList();
    public static List pathy=new ArrayList();
    public static List pathxx=new ArrayList();
    public static List pathyy=new ArrayList();
    public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        while(sc.hasNextInt()){
            int m=sc.nextInt();
            int n=sc.nextInt();

            int[][] arr=new int[m][n];
            int[][] vis=new int[m][n];
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    vis[i][j]=0;
                }

            }

            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    arr[i][j]=sc.nextInt();
                }
            }    

        /*for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }*/    
            dfs(0,0,m,n,arr,vis);
        //System.out.println(pathx.size());
            for(int i=0;i<pathxx.size();i++){
                System.out.println("("+pathxx.toArray()[i]+","+pathyy.get(i)+")");
            }
            pathxx.clear();
            pathyy.clear();
            pathx.clear();
            pathy.clear();

        }
    }
    public static int dfs(int i,int j,int m,int n,int[][] arr,int[][] vis){
        if(i<0 || i>=m || j<0 || j>=n || arr[i][j]==1 ||vis[i][j]==1){
            return 0;
        }
        if(i==m-1&&j==n-1){
            pathx.add(i);
            pathy.add(j);
            //System.out.println(i+" "+j);
            for(int i1=0;i1<pathx.size();i1++){
                pathxx.add(pathx.get(i1));
                pathyy.add(pathy.get(i1));
            }
            return 0;
        }
        /*System.out.println(i+" "+j);
        for(int i1=0;i1<pathx.size();i1++){
            System.out.println(pathx.get(i1));
        }*/
        vis[i][j]=1;
        pathx.add(i);
        pathy.add(j);

        dfs(i+1,j,m,n,arr,vis);
        dfs(i-1,j,m,n,arr,vis);
        dfs(i,j+1,m,n,arr,vis);
        dfs(i,j-1,m,n,arr,vis);
        pathx.remove(pathx.size()-1);
        pathy.remove(pathy.size()-1);
        return 1;
    }
}