洛谷P1141题解：01迷宫连通块问题的BFS解法

2天前洛谷题解56

一、问题分析

题目要求在一个由0和1组成的n×n迷宫中，对于给定的m个查询点，快速回答从该点出发能移动到的格子总数。移动规则是只能移动到相邻且数字不同的格子。

二、算法核心思路

连通块预处理：

使用BFS算法预先计算所有连通块
为每个连通块分配唯一标识
记录每个连通块的大小

查询优化：

预处理后，每个查询可以在O(1)时间内回答
通过查找点的连通块标识直接返回对应大小

边界处理：

使用从1开始的索引简化边界检查
方向数组简化移动逻辑

三、完整代码实现（带注释）

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

int main() {
    ios::sync_with_stdio(false);  // 加速输入输出
    cin.tie(nullptr);             // 解除cin与cout的绑定
    
    int n, m;
    cin >> n >> m;
    
    // 读取迷宫，注意题目行列从1开始
    vector<vector<char>> grid(n+2, vector<char>(n+2));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> grid[i][j];
        }
    }
    
    // 连通块标记和大小统计
    vector<vector<int>> component(n+2, vector<int>(n+2, 0));
    vector<int> component_size(1); // 从1开始计数
    
    int current_component = 0;
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (component[i][j] == 0) {
                current_component++;
                queue<pair<int, int>> q;
                q.push({i, j});
                component[i][j] = current_component;
                int size = 1;
                
                while (!q.empty()) {
                    auto [x, y] = q.front();
                    q.pop();
                    
                    for (int k = 0; k < 4; ++k) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        
                        // 检查边界、未访问且数字相反
                        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n &&
                            component[nx][ny] == 0 && 
                            grid[nx][ny] != grid[x][y]) {
                            component[nx][ny] = current_component;
                            size++;
                            q.push({nx, ny});
                        }
                    }
                }
                component_size.push_back(size);
            }
        }
    }
    
    // 处理查询
    while (m--) {
        int x, y;
        cin >> x >> y;
        cout << component_size[component[x][y]] << "\n";
    }
    
    return 0;
}