文字教学

这道题数据规模大（$n \le 1000, m \le 10^5$），不能对每个询问单独BFS，需用预处理连通块的方法：

1. 连通块定义：所有能通过“0→1或1→0交替移动”互相到达的格子属于同一连通块。
2. 预处理：遍历每个未访问的格子，用BFS找出整个连通块，给连通块内所有格子标记编号，并记录该连通块的大小。
3. 查询：每个询问直接查该格子所在连通块的大小即可。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
char g[N][N];
int vis[N][N], ans[1000010];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int qx[1000010], qy[1000010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        for (int j = 1; j <= n; ++j)
            g[i][j] = s[j-1];
    }
    int id = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (vis[i][j] == 0) {
                id++;
                int h = 0, t = 0;
                qx[t] = i; qy[t] = j; t++;
                vis[i][j] = id;
                int cnt = 1;
                while (h < t) {
                    int x = qx[h], y = qy[h]; h++;
                    for (int d = 0; d < 4; ++d) {
                        int nx = x + dx[d], ny = y + dy[d];
                        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && vis[nx][ny] == 0 && g[nx][ny] != g[x][y]) {
                            vis[nx][ny] = id;
                            cnt++;
                            qx[t] = nx; qy[t] = ny; t++;
                        }
                    }
                }
                ans[id] = cnt;
            }
        }
    }
    while (m--) {
        int i, j;
        cin >> i >> j;
        cout << ans[vis[i][j]] << '\n';
    }
    return 0;
}