详解Java利用深度优先遍历解决迷宫问题

简介

在计算机科学中，深度优先遍历是一种用于遍历或搜索树或图的概念。深度优先遍历会先访问深度最大的节点（或者最右边的节点），然后回溯到该节点的父节点，并开始遍历它的另一个子节点。这个过程会一直持续到所有的节点都被访问为止。

用深度优先遍历算法解决迷宫问题可以思路简单易懂，代码编写也相对比较简单。

实现步骤

1. 定义迷宫

我们可以用二维数组定义迷宫，其中1表示墙壁，0表示道路，只有在0的位置才能进行移动。

int[][] maze = {
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1},
        {1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1},
        {1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1},
        {1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1},
        {1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1},
        {1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1},
        {1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1},
        {1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1},
        {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
    };

2. 定义访问数组

设置一个与迷宫数组同样大小的数组，用于记录节点是否已经访问，避免重复访问。

boolean[][] visited = new boolean[11][12];

3. 定义方向数组

因为只能上下左右进行移动，所以我们可以定义一个方向数组（方便代码编写）。

int[][] direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

4. 实现深度优先遍历

接下来，我们可以编写深度优先遍历的代码。对于每一个节点，我们都先判断该节点是否为墙或是否已经访问过。如果是，则返回false，否则将该节点标记为已访问。

public static boolean dfs(int[][] maze, boolean[][] visited, int row, int col, int[][] direction) {
    if (row == maze.length - 2 && col == maze[0].length - 2) {
        return true; // 如果当前节点已经到达迷宫出口，遍历结束
    }
    visited[row][col] = true; // 标记已经访问

    for (int i = 0; i < 4; i++) { // 遍历四个方向
        int nextRow = row + direction[i][0];
        int nextCol = col + direction[i][1];
        if (maze[nextRow][nextCol] == 0 && !visited[nextRow][nextCol]) {
            if (dfs(maze, visited, nextRow, nextCol, direction)) {
                return true; // 如果找到出口，返回true
            }
        }
    }
    return false; // 如果未找到出口，返回false
}

5. 调用深度优先遍历

最后，我们只需要将入口节点传入深度优先遍历函数即可。

if (dfs(maze, visited, 1, 1, direction)) {
    System.out.println("迷宫可以走出！");
} else {
    System.out.println("迷宫无法走出！");
}

示例说明

示例1

输入：

int[][] maze = {
        {1, 1, 1, 1, 1},
        {1, 0, 0, 0, 1},
        {1, 0, 1, 0, 1},
        {1, 0, 0, 0, 1},
        {1, 1, 1, 1, 1}
    };

输出：

迷宫可以走出！

解释：此时迷宫的出口在(3,3)位置。

示例2

输入：

int[][] maze = {
        {1, 1, 1, 1, 1},
        {1, 0, 0, 0, 1},
        {1, 0, 1, 0, 1},
        {1, 1, 1, 0, 1},
        {1, 1, 1, 1, 1}
    };

输出：

迷宫无法走出！

解释：因为(2,3)和(3,3)是连通的，所以对于每一个节点，在向四个方向探索时都会重复遍历这两个节点，形成了死循环，导致遍历无法结束。