C++信息学奥赛

3. 网格中的BFS实现

在网格问题中（如迷宫求解），每个单元格视为一个节点，通常有上、下、左、右四个可能的邻居。以下是网格中BFS的实现：

// 网格中的BFS实现（迷宫最短路径）
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 方向数组：上、右、下、左
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

// 网格BFS求解最短路径
int bfsGrid(const vector<vector<int>>& grid, 
            pair<int, int> start, 
            pair<int, int> end) {
    int rows = grid.size();
    if (rows == 0) return -1;
    int cols = grid[0].size();
    
    // 检查起点和终点是否合法
    if (grid[start.first][start.second] == 1 || 
        grid[end.first][end.second] == 1) {
        return -1;  // 起点或终点是障碍物
    }
    
    // 记录是否访问过
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    // 记录距离
    vector<vector<int>> distance(rows, vector<int>(cols, -1));
    
    // 创建队列并加入起点
    queue<pair<int, int>> q;
    q.push(start);
    visited[start.first][start.second] = true;
    distance[start.first][start.second] = 0;
    
    // 队列不为空时继续处理
    while (!q.empty()) {
        auto current = q.front();
        q.pop();
        int x = current.first;
        int y = current.second;
        
        // 如果到达终点，返回距离
        if (x == end.first && y == end.second) {
            return distance[x][y];
        }
        
        // 探索四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 检查新位置是否合法且未被访问
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && 
                grid[nx][ny] == 0 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                distance[nx][ny] = distance[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    
    // 无法到达终点
    return -1;
}

int main() {
    // 0表示可通行，1表示障碍物
    vector<vector<int>> grid = {
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 0, 0}
    };
    
    pair<int, int> start = {0, 0};    // 起点
    pair<int, int> end = {4, 4};      // 终点
    
    int shortestPath = bfsGrid(grid, start, end);
    
    if (shortestPath != -1) {
        cout << "从起点到终点的最短路径长度: " << shortestPath << endl;
    } else {
        cout << "无法从起点到达终点" << endl;
    }
    
    return 0;
}