SDJZUOJ迷宫问题（BFS）

### 迷宫问题 BFS 算法模板 以下是基于引用内容构建的一个完整的迷宫问题 BFS 算法模板。该模板适用于求解从起点 `(sx, sy)` 到终点 `(ex, ey)` 的最短路径长度。 #### 数据结构定义 为了实现 BFS，通常需要一个队列来存储当前状态节点的信息。这里可以采用 `struct` 定义节点的状态，并通过数组模拟队列操作[^2]。 ```c++ #include <bits/stdc++.h> using namespace std; // 定义方向向量（上下左右） const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; // 定义节点结构体 struct Node { int x, y, step; Node(int _x, int _y, int _step) : x(_x), y(_y), step(_step) {} }; bool isValid(int nx, int ny, int n, int m, vector<vector<int>> &maze, vector<vector<bool>> &visited) { if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == 0 && !visited[nx][ny]) { return true; } return false; } ``` #### 主函数逻辑 在主函数中初始化队列并执行 BFS 遍历过程。每次扩展时判断新位置是否合法且未访问过，如果是，则将其加入队列继续遍历[^3]。 ```c++ int bfs(int sx, int sy, int ex, int ey, vector<vector<int>> &maze) { int n = maze.size(); int m = maze[0].size(); // 初始化 visited 数组防止重复访问 vector<vector<bool>> visited(n, vector<bool>(m, false)); // 创建队列并将起始点入队 queue<Node> q; q.push(Node(sx, sy, 0)); visited[sx][sy] = true; while (!q.empty()) { Node current = q.front(); q.pop(); // 如果到达目标点则返回步数 if (current.x == ex && current.y == ey) { return current.step; } // 尝试四个方向移动 for (int i = 0; i < 4; ++i) { int nx = current.x + dx[i]; int ny = current.y + dy[i]; if (isValid(nx, ny, n, m, maze, visited)) { visited[nx][ny] = true; q.push(Node(nx, ny, current.step + 1)); } } } // 若无法抵达终点，返回 -1 return -1; } ``` #### 使用示例 下面是一个简单的测试案例展示如何调用上述 BFS 函数： ```c++ int main() { // 输入迷宫地图 vector<vector<int>> maze = { {0, 1, 0, 0}, {0, 1, 0, 1}, {0, 0, 0, 0}, {0, 1, 1, 0} }; int sx = 0, sy = 0; // 起点坐标 int ex = 3, ey = 3; // 终点坐标 int result = bfs(sx, sy, ex, ey, maze); cout << "Minimum steps required: " << result << endl; return 0; } ``` 此代码片段展示了如何利用 BFS 来计算迷宫中最短路径所需的最少步数。