01迷宫

形式化题目

给定一个 $n \times n$ 的 0/1 矩阵 $A$ 。把每个格子看成一个点，两个有公共边的格子之间连一条边，当且仅当它们的数值不同：

(i,j) \sim (i',j') \iff |i - i'| + |j - j'| = 1 \ \text{且}\ A_{i,j} \neq A_{i',j'}

对每个询问 $(i,j)$ ，求点 $(i,j)$ 在这个无向图中所属连通分量的大小。

题面说的“从这一格开始能移动到多少个格子”，就是“从这一点出发能走到的点数”。两格数值不同这个条件交换两端后依然成立，所以这是一张无向图；走到的点集又是传递封闭的，于是答案恰好就是从 $(i,j)$ 出发那一个连通分量的大小。

样例 $n = 2$ 、 $A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ ：四对相邻格子的数值都不同，四条边全在，四个点连成一块，因此每个询问都回答 $4$ 。

暴力解法

思路

最直接的做法是按题面直译：每个询问单独搜一次。

从询问的格子出发做 BFS（DFS 同样可以），每一步只走四邻中数值不同的格子，用 vis 记住本次搜索走过的格子，走完后统计访问了多少格，就是答案。因为图是无向的，“能走到的点”和“能走到起点的点”是同一批，搜索不会漏解。

这份代码就是这条思路的实现：读入迷宫后，对每个询问调用一次 bfs_count，函数内部先清空 vis，再从起点整片搜一遍，返回访问的格子数。

值得注意的一点：迷宫不能按 0/1 简单分区。01 / 10 里 0 和 1 交错摆放，四个格子互相都可达；反过来，相邻同数值的格子之间没有边，但这也并不表示它们不在同一块里——绕一格就能连通。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-09 21:11
 * update_at: 2026-10-09 21:11
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 做法就是按题面直译：每个询问都从询问的格子出发单独 BFS 一次，数出能走到的格子数。
// m 个询问就要搜索 m 次，复杂度 O(m * n^2)，只有小数据跑得动，
// 所以这里专门用来和 main.cpp 对拍，不作为正解。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 暴力只跑小数据，n <= 100，下标、计数都用 int。
const int MAXN = 105; // 暴力只服务小数据，n <= 100 就够用

char g[MAXN][MAXN]; // g[i][j]：迷宫第 i 行第 j 列的字符，行列下标从 1 开始
int vis[MAXN][MAXN]; // vis[i][j]：这一次搜索里格子有没有走过，每次询问前清空
int n, m;

// 四个方向的增量：下、上、右、左
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

// 只清实际用到的 1..n 范围，不必清整个数组
void clear_vis() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            vis[i][j] = 0;
        }
    }
}

// 从 (sx, sy) 出发单独 BFS 一次，返回这一片能走到的格子数（包含起点）
int bfs_count(int sx, int sy) {
    clear_vis();

    queue<pair<int, int> > q;
    q.push(make_pair(sx, sy));
    vis[sx][sy] = 1;

    int cnt = 0;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        int x = cur.first;
        int y = cur.second;
        cnt++;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx < 1 || nx > n || ny < 1 || ny > n) continue; // 走出迷宫
            if (vis[nx][ny]) continue;                          // 这次搜索已经走过
            if (g[nx][ny] == g[x][y]) continue;                 // 只能走到数值不同的相邻格
            vis[nx][ny] = 1;
            q.push(make_pair(nx, ny));
        }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string row;
        cin >> row;
        for (int j = 1; j <= n; j++) {
            g[i][j] = row[j - 1];
        }
    }

    for (int k = 1; k <= m; k++) {
        int i, j;
        cin >> i >> j;
        cout << bfs_count(i, j) << '\n';
    }

    return 0;
}

复杂度

单次搜索最多访问 $n^2$ 个格子，每条内部相邻关系最多被检查两次，所以单次是 $O(n^2)$ ； $m$ 个询问合起来是 $O(m n^2)$ 。vis 数组占用 $O(n^2)$ 空间。

瓶颈

$n \leqslant 1000$ 、 $m \leqslant 100000$ ，于是 $m n^2$ 达到 $10^{11}$ 量级，必然超时。

瓶颈其实不在“搜一次太慢”——搜一次只要 $O(n^2)$ ——而在同一份信息被重复计算：多个询问很可能落在同一个连通块里，它们的答案一模一样，暴力却每次都从头 BFS 一遍，白白多花 $m$ 倍时间。消除这个重复，就是正解的出发点。

正解

思路

关键观察：同一个连通块内所有格子的答案完全相同，都等于这个连通块的大小。

分两步说清为什么：

连通块内任意两点互相可达。题面问的是“从这个格子能走到多少格”，也就是从它出发的可达点个数；块内任意两点可达集合相同，所以答案必然相同。
块内任意一点都走不到块外。若某点能走到块外的格子，那么按连通分量的定义，块外那个格子本来就该属于这一块，矛盾。所以可达集合恰好是整个块，答案就等于块的大小。

把“块内答案相同”这句话当成算法：每个连通块只需要算一次。对每个还没被任何块覆盖过的格子，把它所在的整块 BFS 一遍，数出块的大小，再把这个大小写回块内所有格子。预处理结束后每个格子的答案都躺在表里，询问只剩一次查表。

实现上有两个不显然的决定：

ans[i][j] 同时承担“答案”和“访问标记”。0 表示还没有任何块覆盖它；BFS 过程中先写 -1 表示“已经入队、大小还没定”，避免同一个格子被重复入队；块大小数出来后，再把块内所有格子统一改成这个正整数。
BFS 时把块内格子按访问顺序记进 block_cells，编码成 x * MAXN + y。原因是 BFS 过程中还不知道块最终有多大，只能先把格子存下来，等数完再回填；把坐标压成一个整数比开两个平行数组省事。

正确性靠“一进一出”两条保证：每个格子恰好被某一个连通块认领一次（ans 非 0 就不再入队），且块内回填的大小正是该块的真实格子数，因此查表得到的值与“单独搜一次”完全一致——这也正是对拍要检验的东西。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-09 21:11
 * update_at: 2026-10-09 21:11
 */
// main.cpp：P1141 01迷宫（正式主解）。
// 核心思路：能互相走到的格子构成一个连通块，块内格子的答案完全相同，都等于块的大小。
// 所以不用对每个询问单独搜索：对每个还没处理过的格子做一次 BFS，
// 数出整块大小后一次性写回块内所有格子；之后每个询问只是一次 O(1) 查表。
// 代码分层：read_input / flood_fill / answer，main 只按顺序调用；
// 迷宫和答案这些核心数据放全局，函数之间直接共享。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 本题数据都在 int 范围内（n <= 1000、m <= 100000、块大小 <= 10^6），
// 所以下标、计数和答案统一用 int；迷宫字符用 char 省一半内存。
const int MAXN = 1005; // n <= 1000，多开 5 是给下标 1..n 留出边界冗余，省掉数组越界的判断

char g[MAXN][MAXN];      // g[i][j]：迷宫第 i 行第 j 列的字符 '0' 或 '1'，行列下标从 1 开始
int ans[MAXN][MAXN];     // ans[i][j]：格子 (i,j) 所在连通块的大小；0 表示还没处理过
int block_cells[MAXN * MAXN]; // BFS 时按访问顺序记下当前连通块里的格子，用于后面统一回填答案
int n, m;

// 四个方向的增量：下、上、右、左
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

// 读入 n、m 和 n 行迷宫字符串
void read_input() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string row;
        cin >> row;
        for (int j = 1; j <= n; j++) {
            g[i][j] = row[j - 1]; // 字符串下标从 0 开始，题面行列从 1 开始
        }
    }
}

// 从 (sx, sy) 出发把整个连通块处理完：
// 先 BFS 数出块的大小，并把块内格子编码成 x * MAXN + y 记进 block_cells，
// 最后统一把块大小写回这些格子
void flood_fill(int sx, int sy) {
    queue<pair<int, int> > q; // 队列里是待扩展的格子坐标
    q.push(make_pair(sx, sy));
    ans[sx][sy] = -1; // -1 表示“已经入队、大小还没定”，用它避免同一个格子重复入队

    int block_size = 0;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        int x = cur.first;
        int y = cur.second;

        block_cells[block_size] = x * MAXN + y; // 编码成整数存下来，比两个平行数组省事
        block_size++;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx < 1 || nx > n || ny < 1 || ny > n) continue; // 走出迷宫
            if (ans[nx][ny] != 0) continue;                     // 已经属于某个连通块
            if (g[nx][ny] == g[x][y]) continue;                 // 只能走到数值不同的相邻格
            ans[nx][ny] = -1;
            q.push(make_pair(nx, ny));
        }
    }

    for (int k = 0; k < block_size; k++) {
        int x = block_cells[k] / MAXN;
        int y = block_cells[k] % MAXN;
        ans[x][y] = block_size; // 同一连通块内所有格子答案相同
    }
}

// 依次处理每个还没访问过的格子；它所在的整块会在这一次 flood_fill 里一次算完
void flood_all() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (ans[i][j] == 0) {
                flood_fill(i, j);
            }
        }
    }
}

// 处理 m 个询问：查表输出，每个询问 O(1)
void answer() {
    for (int k = 1; k <= m; k++) {
        int i, j;
        cin >> i >> j;
        cout << ans[i][j] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    flood_all();
    answer();

    return 0;
}

STL 写法

上面的 main.cpp 用固定数组：char g[1005][1005] 存迷宫、int ans[1005][1005] 存答案、queue<pair<int, int> > 存坐标对。C++ 里还能把这些换成 STL 写法，思路一点不变，只是数据的摆放方式不同。

迷宫用 vector<string> 按行存，一行一个字符串：grid[x][y] 直接取字符，不用自己算行宽、也不用管末尾的换行符。答案用 vector<vector<int> >，容量跟着 n 走，不会再出现“数组开多大”的问题。

队列里放的东西也换了。放 pair<int, int> 每次都要 make_pair 构造一个二元组；这里把坐标压平成一个整数 $\text{idx} = x \cdot n + y$ ，队列退化成 queue<int>，出队时用 idx / n 和 idx % n 还原坐标。好处不只是一次内存搬运更小：块内格子也能用同一套下标记进 vector<int> 里，回填答案时直接还原坐标即可。

最后一点是下标基准。vector 从 0 开始，所以这里整个网格都用 0 基下标，读入询问时减一，恰好把题面的 1 基编号换算成内部编号，省得每一处都写 x - 1。

网格本身就已经是一张图，不需要像邻接表那样先建边：扩展时用 dx、dy 试探上下左右四个邻居即可，这也是本题比一般建图题更轻的地方。

对应的 cppbook 章节：vector：能改变长度的数组、queue：先进先出

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-09 21:11
 * update_at: 2026-10-09 21:11
 */
// main-stl.cpp：P1141 01迷宫（STL 写法）。
// 核心思路和 main.cpp 完全一样：能互相走到的格子属于同一个连通块，块内答案都等于块的大小，
// 所以只要对每个格子做一次 BFS 把整块大小写回块内所有格子，询问就能 O(1) 回答。
// 差别在数据怎么放：迷宫用 vector<string> 按行存，取 grid[x][y] 就是第 x 行第 y 列的字符；
// 而网格本身就是一个图，不需要另外建邻接表，扩展时检查上下左右四个相邻格即可。
// 队列里也不放坐标对，而是放压平下标 idx = x * n + y，出队时用 / n、% n 还原坐标。
// 代码分层：read_input / flood_fill / solve / answer，main 只按顺序调用。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 本题数据都在 int 范围内（n <= 1000、m <= 100000、块大小 <= 10^6），
// 所以下标、计数和答案统一用 int。
int n, m;
vector<string> grid;           // grid[x][y]：迷宫第 x 行第 y 列的字符，下标从 0 开始
vector<vector<int> > ans;      // ans[x][y]：格子 (x,y) 所在连通块的大小；0 表示还没处理过
vector<int> block_cells;       // 当前连通块包含的压平下标，用来把块大小统一回填

// 四个方向的增量：下、上、右、左
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

// 读入迷宫；grid 和 ans 都按 n 行 n 列开好
void read_input() {
    cin >> n >> m;

    grid.assign(n, string());
    for (int x = 0; x < n; x++) {
        cin >> grid[x];
    }

    ans.assign(n, vector<int>(n, 0));
}

// 从 (sx, sy) 出发把整个连通块处理完：
// BFS 数出块的大小，同时把块内格子记进 block_cells，最后统一写回答案
void flood_fill(int sx, int sy) {
    queue<int> q; // 队列里是压平下标 idx = x * n + y
    block_cells.clear();

    q.push(sx * n + sy);
    ans[sx][sy] = -1; // -1 表示“已经入队、大小还没定”，用它避免同一个格子重复入队

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        int x = cur / n; // 还原坐标：idx = x * n + y
        int y = cur % n;
        block_cells.push_back(cur);

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // 走出迷宫
            if (ans[nx][ny] != 0) continue;                       // 已经属于某个连通块
            if (grid[nx][ny] == grid[x][y]) continue;             // 只能走到数值不同的相邻格
            ans[nx][ny] = -1;
            q.push(nx * n + ny); // 新格子同样压平后入队
        }
    }

    int block_size = block_cells.size(); // 块的大小就是块内格子个数
    for (int k = 0; k < block_size; k++) {
        int x = block_cells[k] / n;
        int y = block_cells[k] % n;
        ans[x][y] = block_size; // 同一连通块内所有格子答案相同
    }
}

// 依次处理每个还没访问过的格子；它所在的整块会在这一次 flood_fill 里一次算完
void solve() {
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < n; y++) {
            if (ans[x][y] == 0) {
                flood_fill(x, y);
            }
        }
    }
}

// 处理 m 个询问：查表输出，每个询问 O(1)
void answer() {
    for (int k = 0; k < m; k++) {
        int i, j;
        cin >> i >> j;
        cout << ans[i - 1][j - 1] << '\n'; // 题面行列从 1 开始，减一才是 vector 下标
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();
    answer();

    return 0;
}

复杂度

预处理时每个格子恰好入队一次，每条相邻关系最多被检查两次（两端各一次），所以所有 BFS 的时间合计 $O(n^2)$ ； $m$ 个询问每次 $O(1)$ 查表。总时间复杂度 $O(n^2 + m)$ ，空间复杂度 $O(n^2)$ （ans、block_cells 和迷宫本身）。

在 $n = 1000$ 、 $m = 100000$ 的满数据上，main.cpp 实测只有 $0.02 \sim 0.05$ 秒（随机迷宫约 $0.04$ 秒，棋盘交错约 $0.025$ 秒）；同样的数据用暴力按 $O(m n^2)$ 至少要几百秒，两者相差四个数量级。

总结

把问题抽象成图：格子是点，数值不同的相邻格之间连边，询问就是问连通分量大小。
暴力对每个询问单独 BFS，正确但重复：同一连通块被反复搜索， $O(m n^2)$ 无法接受。
关键观察：同一连通块内所有格子答案相同，都等于块的大小；于是把“每个询问搜一次”改成“每个块搜一次”，块大小写回块内所有格子，询问退化成查表。
总复杂度 $O(n^2 + m)$ 。“预处理一次、查询多次”是这类多询问题的通用套路。

图示解析

例子的连通块分解

下面这个 $4 \times 4$ 迷宫用来展示“同块同答案”。左边是迷宫本身，中间把每个格子标上它所属的块编号，右边写上该格子的答案（也就是它所在块的大小）：

迷宫	块编号	答案
`0100` `1101` `1001` `0011`	`A A A B` `A B B B` `B B C C` `B C C D`	`4 4 4 7` `4 7 7 7` `7 7 4 4` `7 4 4 1`

4 个块的大小分别是 $4$ 、 $7$ 、 $4$ 、 $1$ 。预处理只做了 4 次 BFS，而不是等询问来了再做 $m$ 次：例如询问 $(2,2)$ 和 $(3,1)$ 都落在块 B 上，两个询问共享同一次搜索的结果，都回答 $7$ 。右下角的 $(4,4)$ 是 $1$ ，因为它的上邻 $(3,4)$ 和左邻 $(4,3)$ 数值都是 $1$ ，与它相同，四条边一条也画不出去。

预处理与询问的关系

这张图说明正解的执行顺序：先一次预处理把所有块的答案铺满整张表，询问阶段只做查表。

flowchart LR
    A["扫描到未访问格子"] --> B["BFS 整块<br/>数出块大小"]
    B --> C["块大小写回<br/>块内所有格子"]
    C --> D{"还有未访问格子?"}
    D -- 是 --> A
    D -- 否 --> E["读入一个询问"]
    E --> F["查 ans[i][j] 直接输出"]
    F --> G{"还有询问?"}
    G -- 是 --> E
    G -- 否 --> H["结束"]

朴素解里 A -> B 会在每个询问上重复一次；正解把它提前到询问之前，每个格子只入队一次，于是左侧的预处理一共只跑 $O(n^2)$ 步，右侧的询问循环变成纯粹的输出。

目录