【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索

这篇具有很好参考价值的文章主要介绍了【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索

☕前言:

📖📖走迷宫一类的问题一般都是暴力搜索解决,搜索的方法有两种:深度优先(DFS)和广度优先(BFS),而提到DFS就离不开递归,涉及到递归的问题理解起来还是有难度的,代码编写不当很容易造成栈溢出。

🌻🌻今天就用三道走迷宫问题带你彻底搞懂怎么用DFS秒杀迷宫类问题~

题目传送门:🚀🚀🚀

三道练习题目全部来源于计蒜客平台。

题目 链接
迷宫(一) https://nanti.jisuanke.com/t/T1595
迷宫(二) http://nanti.jisuanke.com/t/T1596
迷宫(三) https://nanti.jisuanke.com/t/T1597

🍋走迷宫—DFS深搜:

😎不废话,直接上题,题来~

【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索

🍔迷宫(一):

【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索

一天蒜头君掉进了一个迷宫里面,蒜头君想逃出去,可怜的蒜头君连迷宫是否有能逃出去的路都不知道。

看在蒜头君这么可怜的份上,就请聪明的你告诉蒜头君是否有可以逃出去的路。

输入格式

第一行输入两个整数 n 和 m,表示这是一个 n×m 的迷宫。

接下来的输入一个 n 行 m 列的迷宫。其中 'S' 表示蒜头君的位置,'*'表示墙,蒜头君无法通过,'.'表示路,蒜头君可以通过'.'移动,'T'表示迷宫的出口(蒜头君每次只能移动到四个与他相邻的位置——上,下,左,右)。

输出格式

输出一个字符串,如果蒜头君可以逃出迷宫输出"yes",否则输出"no"

数据范围

1<=n,m<=10。

输出时每行末尾的多余空格,不影响答案正确性

样例输入1

3 4
S**.
..*.
***T

样例输出1

no

样例输入2

3 4
S**.
....
***T

样例输出2

yes

👩🏻‍🏫题目让我们判断给定的迷宫是否有可行解,也就是能否从S走到T,但是不要着急,让我们先来处理一下输入:

⭐先设置两个全局变量n,m用来接收迷宫的行数与列数,同时定义一个全局的二维char数组用来存储迷宫。

public static int n;
public static int m;
public static char[][] maze;

⭐在Java中是不能读入单个字符的,我们可以直接读取一行字符串,再转化为数组,不用担心,字符串转数组在Java中已经封装好了。

⭐注意S的位置题目中并没有说是在左上角,所以在输入的时候还要存储下S的位置。

Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
maze = new char[n][m];
int x = 0, y = 0;
for (int i = 0; i < n; i++) {
	String str = sc.next();
	int start = str.indexOf('S');
 	if (start != -1) {
		x = i;
		y = start;
	}
	maze[i] = str.toCharArray();
}
sc.close();

⭐输入处理好了,现在来思考一下怎么用DFS走迷宫。

⭐在走迷宫时肯定不能走到迷宫外面,不妨写一个方法用来判断现在的位置是否还在迷宫内。

public static boolean inMaze(int x, int y) {
	return (0 <= x && x < n && 0 <= y && y < m);
}

⭐仅仅判断是否在迷宫内还不够,我们在走迷宫时还要防止来回兜圈子,所以还需要一个二维数组用来标记走过的位置,走过某个位置以后就不再走了。

public static boolean[][] vis;

同时在主方法中对数组进行实例化:vis = new boolean[n][m]

⭐有了以上的准备工作,现在我们可以来正式编写DFS的代码了,首先定义一个方法,用来表示搜索到了某个位置,返回值是Boolean类型,用来返回迷宫是否有可行解(当然也可以返回void,用全局变量来表示迷宫是否可行):

public static boolean dfs(int x, int y)

由于后面要用到递归,这里也很容易想到递归出口,走到T就不走了:

if (maze[x][y] == 'T') {
	return true;
}

然后我们可以将当前位置进行标记,并依次尝试上左下右(习惯用逆时针)四个方向是否可以走,递归调用dfs()

public static boolean dfs(int x, int y) {
	//	递归出口
	if (maze[x][y] == 'T') {
		return true;
	}
	//	标记已经走过
	vis[x][y] = true;
	int tx = x - 1, ty = y;
	if (inMaze(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '*') {
	//	可以向这个方向走,并且能走出去,返回true
		if (dfs(tx, ty))
		return true;
	}
	tx = x;
	ty = y - 1;
	if (inMaze(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '*') {
		if (dfs(tx, ty))
			return true;
	}
	tx = x + 1;
	ty = y;
	if (inMaze(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '*') {
		if (dfs(tx, ty))
			return true;
	}
	tx = x;
	ty = y + 1;
	if (inMaze(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '*') {
		if (dfs(tx, ty))
			return true;
	}
	return false;
}

⭐如果你觉得尝试四个方向的代码太长了,还可以简化一下,使用一个数组来表示要走的方向。

public static int[][] dir = new int[][]{
	{-1, 0}, {0, -1}, {1, 0}, {0, 1}
};

使用循环来向四个方向尝试:😉

for (int i = 0; i < 4; i++) {
	int tx = x + dir[i][0];
	int ty = y + dir[i][1];
	if (inMaze(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '*') {
		if (dfs(tx, ty)) {
			return true;
		}
	}
}

⭐将上面的代码组织起来,这道题目就解决了。

🍦AC代码(Java):
import java.util.Scanner;

public class Main {

    public static int n;
    public static int m;
    public static char[][] maze;
    public static boolean[][] vis;
    public static int[][] dir = new int[][]{
        {-1, 0}, {0, -1}, {1, 0}, {0, 1}
    };

    public static boolean inMaze(int x, int y) {
        return (0 <= x && x < n && 0 <= y && y < m);
    }

    public static boolean dfs(int x, int y) {
        if (maze[x][y] == 'T') {
            return true;
        }
        vis[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if (inMaze(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '*') {
                if (dfs(tx, ty)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        maze = new char[n][m];
        vis = new boolean[n][m];
        int x = 0, y = 0;
        for (int i = 0; i < n; i++) {
            String str = sc.next();
            int start = str.indexOf('S');
            if (start != -1) {
                x = i;
                y = start;
            }
            maze[i] = str.toCharArray();
        }
        sc.close();
        String ans = dfs(x, y) ? "yes" : "no";
        System.out.println(ans);
    }
}

【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索


【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索

🌭迷宫(二):

【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索

蒜头君在你的帮助下终于逃出了迷宫,但是蒜头君并没有沉浸于喜悦之中,而是很快的又陷入了思考,从这个迷宫逃出的最少步数是多少呢?

输入格式

第一行输入两个整数 n 和 m,表示这是一个 n×m 的迷宫。

接下来的输入一个 n 行 m 列的迷宫。其中 'S' 表示蒜头君的位置,'*'表示墙,蒜头君无法通过,'.'表示路,蒜头君可以通过'.'移动,'T'表示迷宫的出口(蒜头君每次只能移动到四个与他相邻的位置——上,下,左,右)。

输出格式

输出整数,表示蒜头君逃出迷宫的最少步数,如果蒜头君无法逃出迷宫输出 -1−1。

数据范围

1<=n,m<=10

输出时每行末尾的多余空格,不影响答案正确性

样例输入1

3 4
S**.
..*.
***T

样例输出1

-1

样例输入2

3 4
S**.
....
***T

样例输出2

5

👩🏻‍🏫这道题和上一道题的区别在于它让我们得到迷宫可行解的最少步数,因此我们可以在上一到题的基础上,加入全局变量step用来计数,同时加入minStep全局变量保存最少的步数。

本题我们尝试让函数返回void,并用全局变量flag标记迷宫能否走通。

public static int step = 0;
public static int minStep = Integer.MAX_VALUE;

⭐每走一步,step加一,当走到T时就更新我们的最小路径:

if (maze[x][y] == 'T') {
	minStep = Math.min(minStep, step);
	flag = true;
	return;
}

⭐迷宫的可行解不只有一个,上一题中的dfs()在找到一种方案后就直接返回true了,不会尝试其他走法,因此为了搜索所有方案,我们需要用到深度优先搜索中一个很重要的技巧:回溯

👉🏻回溯简单理解就是在我们每次做出动作后,都要在递归调用的后面撤销刚刚的动作。

比如我们标记了vis[x][y] = true,并让step++,在递归调用后还要将其撤销,这样dfs()函数就会搜索所有可行的方案:

public static void dfs(int x, int y) {
	if (maze[x][y] == 'T') {
		minStep = Math.min(minStep, step);
		flag = true;
		return;
	}
	vis[x][y] = true;
	step++;
	for (int i =0; i < 4; i++) {
		int tx = x + dir[i][0];
		int ty = y + dir[i][1];
		if (in(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '*')
		dfs(tx, ty);
	}
	// 回溯,不然搜出一条可行路径就不会继续搜了
	vis[x][y] = false;
	step--;
}

⭐看到这里的小伙伴是不是以为这道题终于结束了,不要高兴的太早,这里的代码虽然没有问题,但是提交测试会超时,所以我们还需要对dfs()进行剪枝

👉🏻所谓剪枝就是剪掉一些不可能的方案,减少搜索的次数。

👉🏻本题的剪枝比较简单,当我们的步数已经超过之前某个方案得到最小路径时,接着走不可能得到更小的步数,这样的话就没必要继续往下走了,直接让函数返回。

if (step > minStep)
	return;

🍻至此,本题已经搞定了。

AC代码(Java):
import java.util.Scanner;

public class Main {

    public static int n;
    public static int m;
    public static char[][] maze;
    public static boolean[][] vis;
    public static int[][] dir = new int[][]{
        {-1, 0}, {0, -1}, {1, 0}, {0, 1}
    };
    public static boolean flag = false;
    public static int step = 0;
    public static int minStep = Integer.MAX_VALUE;

    public static boolean in(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    }

    public static void dfs(int x, int y) {
        // 剪枝,不然会超时。
        // 当前步数比之前方案的步数还大,这种情况直接排除,不可能是最佳答案。
        if (step > minStep)
            return;
        if (maze[x][y] == 'T') {
            minStep = Math.min(minStep, step);
            flag = true;
            return;
        }
        vis[x][y] = true;
        step++;
        for (int i =0; i < 4; i++) {
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if (in(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '*')
                dfs(tx, ty);
        }
        // 回溯,不然搜出一条可行路径就不会继续搜了
        vis[x][y] = false;
        step--;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        maze = new char[n][m];
        vis = new boolean[n][m];
        int x = 0, y = 0;
        for (int i = 0; i < n; i++) {
            String str = sc.next();
            int j = str.indexOf('S');
            if (j != -1) {
                x = i;
                y = j;
            }
            maze[i] = str.toCharArray();
        }
        sc.close();
        dfs(x, y);
        minStep = flag ? minStep : -1;
        System.out.println(minStep);
    }
}

【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索


【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索

🍟迷宫(三):

【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索

经过思考蒜头君终于解决了怎么计算一个迷宫的最短路问题,于是蒜头君找到一个新的迷宫图,来验证自己是否真的会计算一个迷宫的最短路。

为了检验自己计算的是否正确,蒜头君特邀你一起来计算。

输入格式

第一行输入两个整数 n 和 m,表示这是一个 n×m 的迷宫。

接下来的输入一个 n 行 m 列的迷宫。其中'@'表示蒜头君的位置,'#'表示墙,蒜头君无法通过,'.'表示路,蒜头君可以通过'.'移动,所有在迷宫最外围的'.'都表示迷宫的出口(蒜头君每次只能移动到四个与他相邻的位置——上,下,左,右)。

输出格式

输出整数,表示蒜头君逃出迷宫的最少步数,如果蒜头君无法逃出迷宫输出 -1−1。

数据范围

1<=n,m<=15。

输出时每行末尾的多余空格,不影响答案正确性

样例输入1

9 13
#############
#@..........#
#####.#.#.#.#
#...........#
#.#.#.#.#.#.#
#.#.......#.#
#.#.#.#.#.#.#
#...........#
#####.#######

样例输出1

11

样例输入2

4 6
#.####
#.#.##
#...@#
######

样例输出2

5

🍬这道题主要是对前面两道题目的总结,给大家练下手,学会了前面两道,这道题应该可以秒杀了~

😎不多解释,直接给出代码~

AC代码(Java):
import java.util.Scanner;

public class Main {

    public static int n;
    public static int m;
    public static boolean flag = false;
    public static int step = 0;
    public static int minStep = Integer.MAX_VALUE;
    public static char[][] maze;
    public static boolean[][] vis;
    public static int[][] dir = new int[][]{
        {-1, 0}, {0, -1}, {1, 0}, {0, 1}
    };

    public static boolean in(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    }

    public static void dfs(int x, int y) {
        if (step > minStep)
            return;
        if (maze[x][y] == '.' && (x == 0 || x == n - 1 || y == 0 || y == m - 1)) {
            flag = true;
            minStep = Math.min(minStep, step);
            return;
        }
        vis[x][y] = true;
        step++;
        for (int i = 0; i < 4; i++) {
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if (in(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '#') {
                dfs(tx, ty);
            }
        }
        vis[x][y] = false;
        step--;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        maze = new char[n][m];
        vis = new boolean[n][m];
        int x = 0, y = 0;
        for (int i = 0; i < n; i++) {
            String str = sc.next();
            int j = str.indexOf('@');
            if (j != -1) {
                x = i;
                y = j;
            }
            maze[i] = str.toCharArray();
        }
        sc.close();
        dfs(x, y);
        int ans = flag ? minStep : -1;
        System.out.println(ans);
    }
}

【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索


🍌🍌🍌
看了上面三道题目不知道屏幕前的你对DFS是不是有了更进一步的理解呢?笔者感觉DFS理解起来还是有难度的,希望友友们多加练习哦~
🍍🍍🍍
创作不易,如果觉得本文对你有所帮助的话请动动小手,给博主点个免费的赞吧。🙇🏻‍♀️
🍉🍉🍉
@作者:Mymel_晗,计科专业大学牲菜狗一枚,请大佬们多多关照~

【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索文章来源地址https://www.toymoban.com/news/detail-410607.html

到了这里,关于【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(4)

    目录 写在前面: 题目:P1149 [NOIP2008 提高组] 火柴棒等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤

    2023年04月08日
    浏览(32)
  • 【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(1)

    目录 写在前面: 题目:P1036 [NOIP2002 普及组] 选数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤为重要

    2024年01月23日
    浏览(28)
  • 【AcWing刷题】蓝桥杯专题突破-深度优先搜索-dfs(8)

    目录 写在前面: 题目:1114. 棋盘问题 - AcWing题库 题目描述: 输入格式: 输出格式: 数据范围: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤为重要, 所以,为了学好深度优先搜

    2023年04月09日
    浏览(30)
  • 蓝桥杯算法竞赛系列第五章——拔高篇之深度优先搜索(DFS)

    欢迎回到:遇见蓝桥遇见你,不负代码不负卿!  目录 一、引入:深度优先搜索(DFS)  二、经典例题 例题1.二叉搜索树的范围和 题目描述 题解 代码执行 例题2.岛屿数量  题目描述 题解 代码执行 例题3.背包问题 题目描述 题解 代码执行 三、思考题 四、蓝桥结语:遇见蓝

    2023年04月09日
    浏览(35)
  • 迷宫(蓝桥杯C/C++)dfs详解

    题目描述 下图给出了一个迷宫的平面图,其中标记为 1 的为障碍,标记为 0 的为可以通行的地方。 110000迷宫的入口为左上角,出口为右下角,在迷宫中,只能从一个位置走到这 个它的上、下、左、右四个方向之一。 对于上面的迷宫,从入口开始,可以按 DRRURRDDDR 的顺序通过

    2023年04月08日
    浏览(26)
  • BFS算法(宽度优先搜索)超强解析 BFS迷宫问题图文详解 DFS与BFS的区别

      前情回顾:DFS练习-迷宫(最短路径)问题详解 一波三折 图片+文字 以及你需要会的基础:手搓数据结构之队列queue C/C++语言版(BFS算法预备知识) 广度优先搜索(Breadth First Search)简称广搜或者 BFS, 是遍历图存储结构的一种算法 。 BFS的原理是 “逐层扩散” ,从起点出发

    2024年02月22日
    浏览(38)
  • 172.【华为OD机试】围棋的气(深度优先搜索DFS实现Java&Python&C++&&JS)

    🚀你的旅程将在这里启航!本专栏所有题目均包含优质解题思路,高质量解题代码,详细代码讲解,助你深入学习,深度掌握!

    2024年03月22日
    浏览(67)
  • 269.【华为OD机试真题】解密犯罪时间(深度优先搜索(DFS)-Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年02月21日
    浏览(32)
  • 259.【华为OD机试真题】特殊的加密算法(深度优先搜索(DFS)-Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年02月21日
    浏览(37)
  • 266.【华为OD机试真题】抢7游戏(深度优先搜索DFS-Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年02月22日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包