【蓝桥杯】用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深搜：
😎不废话，直接上题，题来~
🍔迷宫（一）：
一天蒜头君掉进了一个迷宫里面，蒜头君想逃出去，可怜的蒜头君连迷宫是否有能逃出去的路都不知道。
看在蒜头君这么可怜的份上，就请聪明的你告诉蒜头君是否有可以逃出去的路。
输入格式
第一行输入两个整数 nn 和 mm，表示这是一个 n \times mn×m 的迷宫。
接下来的输入一个 nn 行 mm 列的迷宫。其中
'S'表示蒜头君的位置，'*'表示墙，蒜头君无法通过，'.'表示路，蒜头君可以通过'.'移动，'T'表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置——上，下，左，右）。输出格式
输出一个字符串，如果蒜头君可以逃出迷宫输出
"yes"，否则输出"no"。数据范围
1<=n，m<=10。
输出时每行末尾的多余空格，不影响答案正确性
样例输入1
3 4S...*.*T样例输出1
no样例输入2
3 4S.....*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] != '*') {//可以向这个方向走，并且能走出去，返回trueif (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); }}
🌭迷宫（二）：
蒜头君在你的帮助下终于逃出了迷宫，但是蒜头君并没有沉浸于喜悦之中，而是很快的又陷入了思考，从这个迷宫逃出的最少步数是多少呢？
输入格式
第一行输入两个整数 nn 和 mm，表示这是一个 n \times mn×m 的迷宫。
接下来的输入一个 nn 行 mm 列的迷宫。其中
'S'表示蒜头君的位置，'*'表示墙，蒜头君无法通过，'.'表示路，蒜头君可以通过'.'移动，'T'表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置——上，下，左，右）。输出格式
输出整数，表示蒜头君逃出迷宫的最少步数，如果蒜头君无法逃出迷宫输出 -1−1。
数据范围
1<=n，m<=10
输出时每行末尾的多余空格，不影响答案正确性
样例输入1
3 4S...*.*T样例输出1
-1样例输入2
3 4S.....*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); }}
🍟迷宫（三）：
经过思考蒜头君终于解决了怎么计算一个迷宫的最短路问题，于是蒜头君找到一个新的迷宫图，来验证自己是否真的会计算一个迷宫的最短路。
为了检验自己计算的是否正确，蒜头君特邀你一起来计算。
输入格式
第一行输入两个整数 nn 和 mm，表示这是一个 n \times mn×m 的迷宫。
接下来的输入一个 nn 行 mm 列的迷宫。其中
'@'表示蒜头君的位置，'#'表示墙，蒜头君无法通过，'.'表示路，蒜头君可以通过'.'移动，所有在迷宫最外围的'.'都表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置——上，下，左，右）。输出格式
输出整数，表示蒜头君逃出迷宫的最少步数，如果蒜头君无法逃出迷宫输出 -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); }}
🍌🍌🍌
看了上面三道题目不知道屏幕前的你对DFS是不是有了更进一步的理解呢？笔者感觉DFS理解起来还是有难度的，希望友友们多加练习哦~
🍍🍍🍍
创作不易，如果觉得本文对你有所帮助的话请动动小手，给博主点个免费的赞吧。🙇🏻♀️
🍉🍉🍉
@作者：Mymel_晗，计科专业大学牲菜狗一枚，请大佬们多多关照~
