单元最短路径c++bfs

### C++ 实现 BFS 广度优先搜索解决单元格最短路径问题 #### 算法概述 广度优先搜索（BFS）是一种基于队列的图遍历算法，适用于求解无权图上的最短路径问题。通过逐层扩展节点的方式，能够确保首次到达目标节点时所经过的路径是最短的。 在给定的 `n x n` 二进制矩阵中，可以通过 BFS 来计算从左上角 `(0, 0)` 到右下角 `(n-1, n-1)` 的最短畅通路径长度[^2]。为了实现这一功能，可以采用队列存储待访问的坐标点，并记录每个点的距离信息。 --- #### 算法实现步骤说明 以下是使用 C++ 编写的一个典型 BFS 解决方案： ```cpp #include <iostream> #include <queue> #include <vector> using namespace std; // 定义方向向量 (8个方向) const int directions[8][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1} }; int shortestPathBinaryMatrix(vector<vector<int>>& grid) { int n = grid.size(); // 如果起始点或终点不可达，直接返回 -1 if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) return -1; vector<vector<bool>> visited(n, vector<bool>(n, false)); // 访问标记数组 queue<pair<int, int>> q; // 队列存储当前坐标 q.push({0, 0}); // 起点入队 visited[0][0] = true; int pathLength = 1; // 初始化路径长度为1 while (!q.empty()) { int size = q.size(); // 当前层次的节点数 for (int i = 0; i < size; ++i) { pair<int, int> current = q.front(); q.pop(); // 若已到达终点，返回路径长度 if (current.first == n - 1 && current.second == n - 1) return pathLength; // 尝试八个方向移动 for (auto& dir : directions) { int newRow = current.first + dir[0]; int newCol = current.second + dir[1]; // 检查新位置是否合法且未被访问过 if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && !visited[newRow][newCol] && grid[newRow][newCol] == 0) { q.push({newRow, newCol}); visited[newRow][newCol] = true; } } } pathLength++; // 增加一层后的路径长度 } return -1; // 如果无法到达终点，返回 -1 } int main() { vector<vector<int>> grid = { {0, 1, 0, 0, 0}, {1, 1, 0, 1, 0}, {0, 0, 0, 1, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 0, 0} }; cout << "Shortest Path Length: " << shortestPathBinaryMatrix(grid) << endl; return 0; } ``` --- #### 关键点解释 1. **方向向量**：定义了一个二维数组 `directions` 表示八个可能的方向，便于处理八连通的情况[^4]。 2. **边界条件检查**：在每次尝试新的坐标之前，需验证其合法性以及是否已经访问过。 3. **队列操作**：利用标准库中的 `std::queue` 存储待探索的节点，按照 FIFO（先进先出）原则依次处理。 4. **终止条件**：当发现某个节点正好位于终点 `(n-1, n-1)` 时立即返回对应的路径长度；如果整个队列耗尽仍未找到有效路径，则返回 `-1`。 --- #### 时间与空间复杂度分析 - **时间复杂度**: O(N²)，其中 N 是网格的一边大小。因为最多会访问每一个单元一次。 - **空间复杂度**: 同样也是 O(N²)，主要用于保存布尔型访问状态表和队列内的元素。 此方法不仅高效而且易于理解，非常适合初学者学习如何运用 BFS 处理实际编程挑战[^3]。 ---