题解 | #迷宫问题#

使用dfs算法，重点理解“撞墙”后的回溯

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int m=scan.nextInt();
        int n=scan.nextInt();
        int[][] maze=new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                maze[i][j]=scan.nextInt(); //接收迷宫信息
            }
        }

        //使用DFS算法，找到迷宫通道
        List<Position> path=new ArrayList<>();
        dfs(maze,0,0,path);

        //输出迷宫通道
        for(Position p:path){
            System.out.println("("+p.x+","+p.y+")");
        }
    }

    //DFS(Depth First Search)算法
    public static boolean dfs(int[][] maze,int x, int y,List<Position> path){
        //添加已走路径
        path.add(new Position(x,y));
        //标记该点已走过，避免重复走
        maze[x][y]=1;

        //递归结束标记
        if(x==maze.length-1 && y==maze[0].length-1){
            return true;
        }

        //判断是否可以走下一步：不可处边界，不可为1
        //向下走
        if(x+1<=maze.length-1 && maze[x+1][y]==0 && dfs(maze,x+1,y,path)){
            return true;
        }
        //向上走
        if(x-1>=0 && maze[x-1][y]==0 && dfs(maze,x-1,y,path)){
            return true;
        }
        //向右走
        if(y+1<=maze[0].length-1 && maze[x][y+1]==0 && dfs(maze,x,y+1,path)){
            return true;
        }
        //向左走
        if(y-1>=0 && maze[x][y-1]==0 && dfs(maze,x,y-1,path)){
            return true;
        }

        //若发现走到死胡同，则回溯
        path.remove(path.size()-1);//删去错误路径的当前点
        maze[x][y]=0;//之后仍然可以通过其他路径通过当前点
        return false;


    }

    //定义Position记录位置
    static class Position{
        int x;
        int y;
        Position(int x,int y){
            this.x=x;
            this.y=y;
        }
    }

}