使用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;
}
}
}