DFS深度优先搜索解决迷宫问题

• 1、题目描述
• 2、解题思路
• 3、代码实现

上一篇博客讲解了BFS广度优先搜索求解迷宫问题，今天试试DFS深度优先搜索

1、题目描述

  给定一个N×MN\times MN×M的网格迷宫G。G的每个格子要么是道路，要么是障碍物(道路用1表示，障碍物用2表示)。

  一直迷宫的入口位置为(x1,y1)(x_1,y_1)(x1​,y1​)，出口位置为(x2,y2)(x_2,y_2)(x2​,y2​)。问从入口道出口，最多要走多少个格子。

输入描述

  输入第1行包含两个整数N,M，分别表示迷宫的大小

  接下来输入一个N×MN \times MN×M的矩阵。若Gi,j=1G_{i,j}=1Gi,j​=1表示其为道路，否则表示其为障碍物。

  最后一行输入四个整数x1,y1,x2,y2x_1,y_1,x_2,y_2x1​,y1​,x2​,y2​，表示入口的位置和出口的位置。
1≤N,M≤102,0≤Gi,j≤1,1≤x1,x2≤N,1≤y1,y2≤M1\le N,M\le 10^2, 0\le G_{i,j}\le 1,1\le x_1,x_2\le N,1\le y_1,y_2\le M 1≤N,M≤102,0≤Gi,j​≤1,1≤x1​,x2​≤N,1≤y1​,y2​≤M
输出描述

  输出仅一行，包含一个整数表示答案。

  若无法从入口道出口，则输出-1。

输入示例

5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2
1 1 4 3

输出示例

7

2、解题思路

  初始迷宫如下图所示：

  我们大致的想法如下：

• 先判断是否到达目标位置，如果达到目标位置，再试探有无其他更短的路径。
• 如果没有达到目标位置，则找到下一步可以到达的位置，直到找到目标位置。

  我们需要先给出四个方向，并用如下代码代理上下左右四个方向

static int[][] dirs={{0,1},//右{1,0},//下{0,-1},//左{-1,0}//上
};

  在这里我们规定按照顺时针方向(右、下、左、上)去一个个试探相邻的节点，我们试探到一个符合条件的节点，就继续按照顺时针方向接着进行试探，每经过一个节点，都要使用visited[x][y]=true数组来标记该节点已经被访问过。

  如果我们搜索到了终点，此时还需要进行回溯，因为我们走的这条路不一定是路径最短的。回溯的时候每一个经过的节点的访问状态标记为未访问visited[x][y]=false，因为我们每次在搜索的时候都有个是否被访问过的判断，回溯的时候不标记为false，那后面就再过不来了。

  经过尝试我们得到了下面三种方案

  这里并没找全，因为手动模拟搜索再回溯很容易标错，这个需要你自己在草稿纸上模拟一下，这里要是过程全部画出来未免显得不优雅。

3、代码实现

  很明显，这里用递归的话可以减少很多代码量，非递归的写法我后面有时间再尝试下吧，普通版本代码如下：

public class Main {public static int endX;public static int endY;public static int min=Integer.MAX_VALUE; //最小路径长度//迷宫：1表示空地，2表示障碍物public static int[][] a=new int[100][100];//false表示未访问，true表示访问public static boolean[][] visited=new boolean[100][100];public static void main(String[] args) {Scanner scan = new Scanner(System.in);//n行m列int n = scan.nextInt();int m = scan.nextInt();//初始化迷宫for (int i = 1; i <=n ; i++) {for (int j = 1; j <=m ; j++) {a[i][j]=scan.nextInt();//1表示空地，2表示障碍物}}//起点和终点坐标int startX = scan.nextInt();int startY = scan.nextInt();endX = scan.nextInt();endY = scan.nextInt();//从起点开始深度优先搜素，所以先将起点设置为已访问visited[startX][startY]=true;dfs(startX,startY,0);System.out.println(min);}/*** @param x 当前点的x坐标* @param y 当前点的y坐标* @param step 经过的步数*/public static void dfs(int x,int y,int step){if(x==endX&&y==endY){   //判断是否走到终点if(step   //如果比最短路径小，更新最短路径min=step;}return; //回溯}//顺时针试探：右、下、左、上//右if(a[x][y+1]==1&& !visited[x][y + 1]){  //是道路且没有被访问过visited[x][y+1]=true;   //将右边的点设置为已访问dfs(x,y+1,step+1);//继续从右边这个点进行深度优先搜索//当上一步dfs执行完，回退的时候需要将这个点设置为未访问visited[x][y+1]=false;}//下if(a[x+1][y]==1&& !visited[x + 1][y]){visited[x+1][y]=true;   //将下边的点设置为已访问dfs(x+1,y,step+1);//继续从下边这个点进行深度优先搜索//当上一步dfs执行完，回退的时候需要将这个点设置为未访问visited[x+1][y]=false;}//左if(a[x][y-1]==1&& !visited[x][y - 1]){visited[x][y-1]=true;   //将左边的点设置为已访问dfs(x,y-1,step+1);//继续从左边这个点进行深度优先搜索//当上一步dfs执行完，回退的时候需要将这个点设置为未访问visited[x][y-1]=false;}//上if(a[x-1][y]==1&& !visited[x-1][y]){visited[x-1][y]=true;   //将上边的点设置为已访问dfs(x-1,y,step+1);//继续从上边这个点进行深度优先搜索//当上一步dfs执行完，回退的时候需要将这个点设置为未访问visited[x-1][y]=false;}return;//回退}
}

  这里的dfs函数中关于右、下、左、上四个方向的探索还能再优化，现在这样写存在大量看起来重复的代码。

  不知道你发现了没有，上面这段代码我们并没有判断索引越界的情况它也没报错。因为我们if里面的判断条件一直是看是否等于1，visited[x][y]是否为false。而我们的二维数组a[100][100]默认初始化是全为0的，所以边界外的a[i][j]全为0，不符合条件。我们是a[1][1]走的，a[0][0]并没有使用，所以即使从起点向左向上也不会越界。

  不明白就看下面这种优化后的，下面的代码加了边界判断思路会更清楚。

  优化版本如下：

import java.util.Scanner;
public class Main {public static int endX;public static int endY;public static int min=Integer.MAX_VALUE; //最小路径长度//迷宫：1表示空地，2表示障碍物public static int[][] a;//false表示未访问，true表示访问public static boolean[][] visited;//定义四个方向public static int[][] dirs={{0,1},//右{1,0},//下{0,-1},//左{-1,0}//上};public static void main(String[] args) {Scanner scan = new Scanner(System.in);//n行m列int n = scan.nextInt();int m = scan.nextInt();a=new int[n+1][m+1];visited=new boolean[n+1][m+1];//初始化迷宫for (int i = 1; i <=n ; i++) {for (int j = 1; j <=m ; j++) {a[i][j]=scan.nextInt();//1表示空地，2表示障碍物}}//起点和终点坐标int startX = scan.nextInt();int startY = scan.nextInt();endX = scan.nextInt();endY = scan.nextInt();//从起点开始深度优先搜素，所以先将起点设置为已访问visited[startX][startY]=true;dfs1(startX,startY,0);System.out.println(min);}//优化版本public static void dfs1(int x,int y,int step){if(x==endX&&y==endY){   //判断是否走到终点if(step   //如果比最短路径小，更新最短路径min=step;}return; //回溯}//顺时针试探：右、下、左、上for (int[] dir : dirs) {//计算出下一个试探位置int tx=x+dir[0];int ty=y+dir[1];//判断是否超出边界 tx<1||tx>n||ty<1||ty>m  下面这样写是因为n和m传不进来，硬传代码不优雅if(tx<1||tx>a.length-1||ty<1||ty>a[0].length-1){continue;}//判断是否是墙if(a[tx][ty]==2){continue;}//如果试探位置未被访问，且是空地if(a[tx][ty]==1&& !visited[tx][ty]){visited[tx][ty]=true;//设置已访问dfs1(tx,ty,step+1);visited[tx][ty]=false;}}return;//回退}
}