☕前言：

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

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

题目传送门：🚀🚀🚀

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

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

---

🍋走迷宫—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);
    }
}

---

🌭迷宫（二）：

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

输入格式

第一行输入两个整数 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);
    }
}

---

🍟迷宫（三）：

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

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

输入格式

第一行输入两个整数 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);
    }
}

---

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