深度优先算法--之模拟迷宫

深度优先算法的基本框架：

void  DFS(int temp){
       临界条件判断//本迷宫临界条件就是迷宫的终点

        尝试每一种可能 for(int i=0;i<n;i++){
           继续下一步DFS(temp+1);

   }

   返回

}

   

public class Algorithm{

//1表示障碍物 ，0表示可走

static int [][]n={{0,0,1,0},{0,0,0,0},{0,0,1,0},{0,1,0,0},{0,0,0,1}};

     // 用来做标记的book函数

static int [][]book=new int[n.length][n[0].length];

    //  开始位置

static int []start={0,0};

     //结束位置

static int []end={3,2};

//定义右 下 左 上

static int [][]next={{0,1},{1,0},{0,-1},{-1,0}};
public static void main(String[] args) {
for(int i=0;i<n.length;i++){
for(int j=0;j<n[0].length;j++){
if(n[i][j]==1)
book[i][j]=2;//只为了在book中作为障碍物显示
}
}
book[0][0]=1;//初始位置标记一下，已走过
dfs(0,0);
}

private static void dfs(int x, int y) {

                 //临界条件

if(x==3&&y==2){
for(int i=0;i<n.length;i++){
for(int j=0;j<n[0].length;j++){
System.out.print(book[i][j]+" ");
}
System.out.println();
}
System.out.println();
return;
}
for(int k=0;k<4;k++){
//计算下个坐标
int dx=x+next[k][0];
int dy=y+next[k][1];
//判断是否越界
if(dx<0||dx>=n[0].length||dy<0||dy>=n[0].length)
continue;
//判断是否为障碍物或已经在路径中
if(book[dx][dy]==0&&n[dx][dy]==0){
book[dx][dy]=1;
dfs(dx,dy);
book[dx][dy]=0;//尝试结束，取消这个点的标记
}
}

}
}