洪水填充算法走迷宫

使用洪水填充算法走迷宫是一种有效的方法，尤其是在解决迷宫中的“可达性”问题时。洪水填充算法可以用来标记迷宫中从起点出发可以到达的所有位置，最终找到从起点到终点的路径。

基本思路

1. 起点：从迷宫的起点出发，开始填充。

2. 相邻节点扩展：检查当前节点的相邻节点（上下左右），如果该节点是通道且未被访问过，则将其加入到队列中进行填充。

3. 终点检查：在填充过程中，如果某个节点是终点，说明找到了从起点到终点的路径。

4. 路径重构：可以通过回溯的方法从终点反向寻找起点，重构路径。

C++代码实现

下面的代码实现了一个简单的迷宫求解器，使用了广度优先搜索（BFS），这是洪水填充算法的一种应用。

#include <iostream>
#include <queue>
#include <vector>
#include <stack>

using namespace std;

struct Point {
    int x, y;
};

// 判断点是否在迷宫范围内，并且是否为通道
bool isValid(int x, int y, const vector<vector<int>>& maze, const vector<vector<bool>>& visited) {
    int rows = maze.size();
    int cols = maze[0].size();
    return (x >= 0 && x < rows && y >= 0 && y < cols && maze[x][y] == 0 && !visited[x][y]);
}

// 使用洪水填充算法走迷宫，找到从起点到终点的路径
bool floodFillMaze(vector<vector<int>>& maze, Point start, Point end) {
    int rows = maze.size();
    int cols = maze[0].size();

    // 方向数组，表示上下左右四个方向
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    // 用于记录每个点是否被访问过
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));

    // 用于记录路径的前一个点
    vector<vector<Point>> prev(rows, vector<Point>(cols, {-1, -1}));

    queue<Point> q;
    q.push(start);
    visited[start.x][start.y] = true;

    while (!q.empty()) {
        Point current = q.front();
        q.pop();

        // 如果到达终点，开始重构路径
        if (current.x == end.x && current.y == end.y) {
            stack<Point> path;
            while (current.x != start.x || current.y != start.y) {
                path.push(current);
                current = prev[current.x][current.y];
            }
            path.push(start);

            cout << "Path from start to end:" << endl;
            while (!path.empty()) {
                Point p = path.top();
                path.pop();
                cout << "(" << p.x << ", " << p.y << ") ";
            }
            cout << endl;
            return true;
        }

        // 扩展到相邻的四个方向
        for (auto& dir : directions) {
            int nx = current.x + dir[0];
            int ny = current.y + dir[1];

            if (isValid(nx, ny, maze, visited)) {
                q.push({nx, ny});
                visited[nx][ny] = true;
                prev[nx][ny] = current;
            }
        }
    }

    cout << "No path found." << endl;
    return false;
}

int main() {
    vector<vector<int>> maze = {
        {0, 1, 0, 0, 0, 0},
        {0, 1, 0, 1, 1, 0},
        {0, 0, 0, 0, 0, 0},
        {0, 1, 1, 1, 1, 1},
        {0, 0, 0, 0, 0, 0},
        {0, 1, 1, 1, 1, 0}
    };

    Point start = {0, 0}; // 起点
    Point end = {5, 5};   // 终点

    floodFillMaze(maze, start, end);

    return 0;
}

代码解释

1. 结构体 Point：

• 用于表示迷宫中的一个点，包含x和y坐标。

2. 函数 isValid：

• 检查给定的坐标是否在迷宫的有效范围内，并且是通道（值为0）且未被访问过。

3. 函数 floodFillMaze：

• 使用广度优先搜索（BFS）来模拟洪水填充算法。

• queue<Point>用于存储当前正在处理的迷宫节点。

• visited数组标记已经访问过的节点，防止重复访问。

• prev数组记录每个节点的前一个节点，用于路径重构。

4. 路径重构：

• 当找到终点时，通过回溯prev数组从终点回到起点，重构并输出路径。

5. 主函数 main：

• 初始化一个迷宫，其中0表示通道，1表示墙壁。

• 指定起点和终点，调用floodFillMaze函数寻找路径。

输出示例

程序运行后，将输出从起点到终点的路径，如果存在的话。输出的路径是一系列从起点到终点的坐标序列。

注意

• 迷宫中的0表示通道，1表示墙壁。

• 程序找到的是一条可行路径，可能不是最短路径，但在BFS的情况下，通常是最短路径。