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

举报
别团等shy哥发育 发表于 2023/04/04 23:07:13 2023/04/04
【摘要】 @toc上一篇博客讲解了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​)。问从入口道出口,最多要走多少个格子。输入描...

@toc

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

1、题目描述

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

一直迷宫的入口位置为 ( x 1 , y 1 ) (x_1,y_1) ,出口位置为 ( x 2 , y 2 ) (x_2,y_2) 。问从入口道出口,最多要走多少个格子。

输入描述

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

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

最后一行输入四个整数 x 1 , y 1 , x 2 , y 2 x_1,y_1,x_2,y_2 ,表示入口的位置和出口的位置。

1 N , M 1 0 2 , 0 G i , j 1 , 1 x 1 , x 2 N , 1 y 1 , y 2 M 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-20230312212540153

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

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

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

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

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

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。