01迷宫(01 Maze) 题解

思路分析

相邻移动关系（0 与 1 互达）是对称的，因此整个迷宫被划分为若干个极大连通块，同一连通块内所有格子的答案均等于该连通块的大小！若每次询问都重新 BFS 会达到 $O(mn^2)$ 超时；正确做法是先对全图做一次 BFS 染色，求出每个格子所属连通块编号 comp[i][j] 及该块大小 sz[id]，随后每次询问 $O(1)$ 查表输出。总时间复杂度 $O(n^2 + m)$。

参考代码

#include <iostream>
#include <queue>
#include <string>
#include <utility>
using namespace std;

string g[1005];
int compId[1005][1005];
int compSz[1000005];
const int DR[4] = {-1, 1, 0, 0};
const int DC[4] = {0, 0, -1, 1};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 0; i < n; ++i) cin >> g[i];

    int tot = 0;
    queue<pair<int, int>> q;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (compId[i][j] != 0) continue;
            ++tot;
            int cnt = 0;
            compId[i][j] = tot;
            q.push({i, j});
            while (!q.empty())
            {
                auto cur = q.front();
                q.pop();
                ++cnt;
                for (int d = 0; d < 4; ++d)
                {
                    int ni = cur.first + DR[d], nj = cur.second + DC[d];
                    if (ni >= 0 && ni < n && nj >= 0 && nj < n && compId[ni][nj] == 0 && g[ni][nj] != g[cur.first][cur.second])
                    {
                        compId[ni][nj] = tot;
                        q.push({ni, nj});
                    }
                }
            }
            compSz[tot] = cnt;
        }
    }

    for (int k = 0; k < m; ++k)
    {
        int r, c;
        cin >> r >> c;
        cout << compSz[compId[r - 1][c - 1]] << "\n";
    }
    return 0;
}