首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >DFS深度优先搜索解决迷宫问题

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

作者头像
别团等shy哥发育
发布2023-03-14 11:34:03
7270
发布2023-03-14 11:34:03
举报

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

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

1、题目描述

  给定一个

N\times M

的网格迷宫G。G的每个格子要么是道路,要么是障碍物(道路用1表示,障碍物用2表示)。

  一直迷宫的入口位置为

(x_1,y_1)

,出口位置为

(x_2,y_2)

。问从入口道出口,最多要走多少个格子。

输入描述

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

  接下来输入一个

N \times M

的矩阵。若

G_{i,j}=1

表示其为道路,否则表示其为障碍物。

  最后一行输入四个整数

x_1,y_1,x_2,y_2

,表示入口的位置和出口的位置。

1\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。

输入示例

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、解题思路

  初始迷宫如下图所示:

image-20230313120157567
image-20230313120157567

  我们大致的想法如下:

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

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

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

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

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

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

image-20230313120221042
image-20230313120221042

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

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){   //如果比最短路径小,更新最短路径
                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){   //如果比最短路径小,更新最短路径
                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;//回退
    }
}
image-20230313120852460
image-20230313120852460
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2023-03-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • DFS深度优先搜索解决迷宫问题
  • 1、题目描述
  • 2、解题思路
  • 3、代码实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档