迷宫问题的非递归c++

迷宫问题通常涉及到路径寻找算法，其中一种常见的非递归解决方案是使用广度优先搜索（BFS），也称为宽度优先搜索。以下是使用C++实现迷宫问题的一种非递归版本：

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

// 定义迷宫的结构
struct Cell {
    bool visited; // 是否访问过
    bool is_wall; // 走廊还是墙壁
};

// 使用邻接矩阵表示迷宫
const int ROWS = N; // 迷宫行数
const int COLS = M; // 迷宫列数
std::vector<std::vector<Cell>> maze(ROWS, std::vector<Cell>(COLS));

// 初始化起点 (0, 0) 和终点 (ROWS - 1, COLS - 1)
Cell start = {false, false};
Cell end = {false, false};

bool is_valid(int row, int col) {
    return row >= 0 && row < ROWS && col >= 0 && col < COLS && !maze[row][col].is_wall;
}

void bfs(int start_row, int start_col) {
    std::queue<pair<int, int>> q;
    maze[start_row][start_col].visited = true;

    q.push({start_row, start_col});

    while (!q.empty()) {
        auto [row, col] = q.front();
        q.pop();

        if (row == end.row && col == end.col) {
            std::cout << "找到了从起点到终点的路径!" << std::endl;
            break;
        }

        for (int dr = -1; dr <= 1; ++dr) {
            for (int dc = -1; dc <= 1; ++dc) {
                int new_row = row + dr;
                int new_col = col + dc;

                if (is_valid(new_row, new_col)) {
                    maze[new_row][new_col].visited = true;
                    q.push({new_row, new_col});
                }
            }
        }
    }
}

int main() {
    // 初始化迷宫和起点、终点位置...
    bfs(start.row, start.col);
    return 0;
}

在这个例子中，我们首先定义了一个`Cell`结构体用于存储每个网格的位置及其状态。然后，使用一个队列（`std::queue`）来进行BFS，每次从当前节点出发，探索其相邻未访问过的节点，直到找到终点。