企业官网建设流程全解析

1. 先把题目看透：H.Maze到底在问什么

这道题出自哈尔滨理工大学软件与微电子学院程序设计竞赛，题名H.Maze，光看名字很容易让人以为是走迷宫求最短路径，实际上它考的是一个更基础的经典问题：网格上的连通块查询。

题目大概长这样：给你一个n行m列的0/1矩阵，0表示可通行的空地，1表示障碍物（墙）。然后给你q个查询，每个查询给一个坐标，问你：包含这个坐标格子的最大空白连通区域有多大。换句话说，就是从这个格子出发，沿着上下左右四个方向走，能到达多少个0格子，并且要求这些0格子互相连通。

为什么要单独写一篇这东西？因为这类题在算法竞赛里太常见了，而且它背后牵扯出来的Flood Fill预处理、BFS队列优化、并查集对比、离线查询思路，几乎是一整套网格题的基础功。很多同学第一次遇到这种“多次查询连通块大小”的题目时，第一反应是每次查询都重新搜一遍，结果大数据直接超时。这篇文章就把从读题到AC的完整链路拆开讲清楚，适合正在刷网格题、刚接触连通块问题的选手参考，也适合准备校赛和省赛的朋友当作复习材料。

我当时拿到这题的第一感觉是：题目描述很直白，没有绕弯子，但越是这样越要警惕数据规模。果然，n、m、q都给得比较大，朴素做法必炸，必须走预处理路线。

2. 核心思路拆解：连通块预处理为什么是正解

2.1 从“每次查询都搜”到“一次全算好”

先说最直观的朴素做法：对于每个查询坐标，从那里做一次BFS或者DFS，数一数能延伸到多少个0格子。这个思路本身没错，错在复杂度上。假设网格是1000x1000，查询有10万次，每次BFS最坏要遍历整个网格，也就是100万个格子，总操作量是10万乘以100万，等于1000亿，这显然不是几秒钟能跑完的量级。

那怎么优化？关键就在于发现一个事实：同一个连通块里的所有格子，答案是一样的。一个连通的空白区域，不管查询其中哪个格子，能到达的区域大小都一样。既然这样，何必每次查询都重新搜？不如一开始就把所有连通块都找出来，给每个连通块编个号，记录它的大小，然后查询的时候直接查表。

这个思路在算法竞赛里叫“预处理+O(1)查询”，本质上是空间换时间。第一次遍历整个网格，用Flood Fill（洪水填充）算法把所有连通的0格子染成同一个颜色（这里是同一个编号），同时统计每个颜色块的大小。之后每个查询点，只要看看它属于哪个编号的块，直接输出那个块的大小即可。

2.2 网格数据结构的建模细节

写代码之前，先想清楚怎么存地图和状态。我习惯用三个二维数组：

• grid：存原始0/1值
• visited：标记某个格子是否被访问过
• block_id：记录每个格子所属的连通块编号

有的选手想省内存，把visited合并到block_id里——比如block_id为0表示“未访问的空地”。这样做理论上可行，但代码可读性会下降，而且容易和真正的块编号混淆。我建议新手阶段老老实实用两个数组，等熟练了再考虑合并。

还有一个容易忽略的细节是坐标系的约定。题目说n行m列，查询给的是“行 列”还是“列 行”，一定要在写代码前确认。我这次统一用(row, col)的语义，避免用(x, y)造成混淆。坐标系的坑一旦踩进去，调试起来非常痛苦，因为错误往往不是RE，而是WA——程序能跑，结果不对，又看不出哪里错。

2.3 连通块编号与面积记录

具体做法是：遍历整个网格的每一个格子，如果发现一个格子是0而且没有被访问过，就从这个格子出发做一次BFS，把整个连通区域都访问一遍，并给它们赋予同一个新的块编号。同时用一个数组记录每个块的大小。

这里有一个新手必踩的坑：visited的标记时机和计数时机必须一致。我推荐的模式是：格子入队时立即标记visited，出队时进行计数。这样能保证每个格子恰好被访问一次、恰好被计数一次。如果你在入队时不标记，等到出队才标记，同一个格子可能会被多次加入队列，导致统计出来的连通块大小偏大，而且BFS的效率也会大打折扣。

再看一下伪代码层面的思路：

for i in range(n): for j in range(m): if grid[i][j] == 0 and not visited[i][j]: new_id += 1 queue = deque([(i, j)]) visited[i][j] = True block_id[i][j] = new_id cnt = 0 while queue: x, y = queue.popleft() cnt += 1 # 检查四个方向，把相邻的0格子入队并标记 block_size.append(cnt)

这样一次遍历之后，所有连通块的信息都在手里了。回答查询的时候，只需要看block_id[query_r][query_c]，然后输出block_size里面对应的值，时间复杂度是O(1)。

3. 三种解法的对比与选型思考

3.1 朴素逐点BFS：必然超时的思路

先把这个方案彻底否掉，因为它最直观也最容易把人带沟里。对每个查询点单独BFS，复杂度是O(q * n * m)。如果题目分了子任务，比如部分数据n、m都很小，这种写法能拿一点分，但一旦数据规模上来就必挂。

我当时在比赛里见过一个选手，第一版就是这个朴素做法，小数据过了，大数据TLE，然后他在那边纠结是是不是Python太慢。其实不是语言的问题，是算法复杂度就摆在那，换C++也救不回来。结论是：只要题目保证查询次数多、网格不小，就必须预处理。

3.2 离线查询逐格合并：看似聪明实则低效

还有一种思路：把查询离线排序，然后针对每个查询动态扩展。这个方案比朴素BFS稍微聪明一点，但本质上还是围绕查询点做搜索，并没有利用“同一连通块答案相同”这个核心性质。它的复杂度在最坏情况下依旧会退化到接近O(q * n * m)。

我在做题时不会优先考虑这种方案，因为它既没有朴素方案那么好写，又没有预处理方案那么高效，处在尴尬的中间地带。如果面试或者比赛里时间紧张，直接选最稳妥的预处理方案就好，不要在这种中间方案上浪费时间。

3.3 Flood Fill BFS vs 并查集

预处理连通块还可以用并查集（DSU）来做：把每个0格子当成一个独立集合，然后遍历每个格子的右邻和下邻，如果两边都是0，就把它们merge到一起。最后每个集合的size就是连通块大小。回答查询时，找到该格子的代表元素，输出集合大小。

两种方案的时间复杂度几乎一致，空间也差不多，真正的区别在于代码风格和出错概率。我个人更推荐BFS + Flood Fill，原因有三个：

1. 思路线性，不需要理解并查集的路径压缩和按大小合并。
2. 可以顺便把每个格子所属的块编号记录下来，查询时直接索引，非常直白。
3. 遍历顺序和地图方向数组的结合很自然，不容易漏边界。

当然，如果你对并查集非常熟练，用并查集也完全没问题。我见过很多高水平选手喜欢用并查集，因为这类题的查询点有时比较复杂，并查集处理“临时拆墙”类变种时更灵活。最终选型看个人熟练度，没有绝对的对错。

4. 完整代码实现与性能优化要点

4.1 可直接参考的Python题解

下面这段代码是我这次用的版本，去掉了本地调试用的注释，保留了核心逻辑。适合作为参考，但不建议直接抄完就跑，最好自己敲一遍。

import sys from collections import deque def solve(): input = sys.stdin.readline n, m, q = map(int, input().split()) grid = [list(map(int, input().split())) for _ in range(n)] queries = [tuple(map(int, input().split())) for _ in range(q)] dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)] visited = [[False] * m for _ in range(n)] block_id = [[0] * m for _ in range(n)] block_size = [0] # 下标从1开始用 current_id = 0 for i in range(n): for j in range(m): if grid[i][j] == 0 and not visited[i][j]: current_id += 1 dq = deque() dq.append((i, j)) visited[i][j] = True block_id[i][j] = current_id cnt = 0 while dq: x, y = dq.popleft() cnt += 1 for dx, dy in dirs: nx, ny = x + dx, y + dy if 0 <= nx < n and 0 <= ny < m: if grid[nx][ny] == 0 and not visited[nx][ny]: visited[nx][ny] = True block_id[nx][ny] = current_id dq.append((nx, ny)) block_size.append(cnt) out = [] for r, c in queries: # 本题保证查询点一定是空地，但加上障碍物判断更稳妥 if grid[r][c] == 1: neighbor_ids = set() for dx, dy in dirs: nr, nc = r + dx, c + dy if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == 0: neighbor_ids.add(block_id[nr][nc]) total = 1 for sid in neighbor_ids: total += block_size[sid] out.append(str(total)) else: out.append(str(block_size[block_id[r][c]])) sys.stdout.write("\n".join(out)) if __name__ == "__main__": solve()

这块代码有几个关键决策值得说明。

使用sys.stdin和sys.stdout：Python的内置input()和print()在数据量大时性能很差。q到10万级别，print逐行输出会带来大量I/O开销，直接TLE。用sys.stdin.readline读行、用sys.stdout.write一次性输出，是竞赛Python选手的基础操作。

用deque而不是list：BFS的队列弹出如果用list.pop(0)，每次弹出都是O(n)操作，因为要移动整个列表。用deque的popleft()是O(1)。这个优化对BFS的性能影响极大，尤其当连通块很大时，队列长度可能达到上万，频繁pop(0)的累计开销能把算法拖慢一个数量级。

visited和block_id分开：虽然从逻辑上可以用block_id是否为0来判断是否访问过，但那样写容易出bug——比如某个格子确实被访问过，但它的block_id就是0吗？不会，因为编号从1开始。但把两个数组分开，语义更清晰，排错更容易。对初学者来说，清晰比省一点内存更重要。

4.2 复杂度分析与边界情况的推演

算法整体分两阶段：

• 预处理阶段：每个格子最多被访问一次，每次访问固定检查4个方向，所以时间复杂度是O(n*m)。
• 查询阶段：每个查询点直接查数组，复杂度O(1)，总O(q)。

整体时间复杂度O(nm+q)，空间复杂度O(nm)。n*m如果达到100万级别，需要大约三个二维整型数组，每个数组在C++里约4MB，Python里的内存开销会大不少，但一般OJ给的内存限制128MB或256MB都够用。

还有一个边界情况需要留意：当查询点本身就是障碍物时怎么办。原题通常保证查询点一定是空地，但作为通用解法，我在代码里加了判断。如果查询点是1，就把它临时当成可以打破的墙，收集它上下左右四个相邻连通块的大小，去重后求和，再加1（它自己）。这种处理方式在多道变种题里都适用，比如“拆墙后最大连通块”的类型。

4.3 追求极限性能时的读入优化方案

如果数据量特别大，或者用的语言是Python，还有一个常用的进阶优化：用sys.stdin.buffer.read一次性读入所有数据，然后统一按空白字符切分。这个方案能把输入时间压缩到极致，但代码可读性会下降。

import sys def solve_fast(): data = list(map(int, sys.stdin.buffer.read().split())) it = iter(data) n = next(it) m = next(it) q = next(it) grid = [[next(it) for _ in range(m)] for _ in range(n)] queries = [(next(it), next(it)) for _ in range(q)] # 后续逻辑相同

这个写法的好处是只有一次系统调用，Python在OJ上的性能能提升不少。缺点是初学者容易看晕，所以我自己平时会先写清晰版保证正确，再用这种快速读入压时间。竞赛里正确性和性能的权衡，需要根据题目数据规模灵活掌握。

5. 调试过程中踩过的坑和现场心得

5.1 坐标顺序：最容易犯的低级错误

我这次第一次写的时候，把查询输入解析成了(x, y)而不是(row, col)，导致后面所有逻辑看起来都对，但输出全错。这种错误最可怕的地方在于它不报RE，程序正常运行，结果却是错的。排查了半天才发现是行列理解反了。

后来我给自己定了一个规矩：只要是网格题，变量名一律用r和c表示行和列，不用x和y。x和y在数学坐标系里容易让人下意识认为第一个是列、第二个是行，而在矩阵里第一个维度的语义是行。这个习惯帮我避开了很多类似的坑。

5.2 边界条件写反：n和m不能混

0 <= nx < n和0 <= ny < m，这里n是行数、m是列数。当n和m不相等时，写在边界判断里的顺序一旦搞反，程序就会越界访问或者漏掉合法格子。Python里数组越界会直接抛IndexError，好一点；C++里就是未定义行为，可能随机出错。我的办法是：写BFS之前先在心里默念三遍“行数n、列数m”，然后定义两个常量行数、列数。如果代码里出现数字的地方都用常量，这种错误基本不会发生。

5.3 从TLE到AC：一个队列的差距

这是我这次做题最直观的感受。第一版用的是list当队列，交上去TLE了一个点。我当时还在想是不是算法复杂度算错了，后来仔细分析才发现是list.pop(0)惹的祸。当连通块很大时，队列里可能有几千个元素，pop(0)每次都要把整个列表往前挪，复杂度变成O(k^2)。换成deque之后，运行时间直接降到原来的十分之一不到。

在OJ上遇到TLE，不要急着怀疑算法整体，先检查几个常见的性能陷阱：

顺带一提，DFS递归在Python里默认递归深度只有1000左右，网格题一旦矩阵稍大，递归直接爆栈。所以我这次从头到尾用的都是BFS，既避免爆栈，又能配合deque获得稳定性能。

5.4 对拍验证：保证正确性的黄金手段

写算法题最怕的是样例过了但提交WA。我自己有个习惯：正式提交前写一个朴素暴力版，然后用随机数据对拍。这次也是这样，我写了一个逐点BFS的暴力版，再和预处理版对比输出，跑了几万组随机小数据，确认输出完全一致才敢提交。

对拍代码本身不复杂，无非是生成随机矩阵、随机查询，然后分别跑两个函数比较输出。关键是这个习惯能帮你在自己的电脑上提前发现逻辑错误，而不是在OJ上反复罚时。对准备竞赛的朋友，这个习惯越早养成越好。

6. 由这道题延伸出去的网格连通性问题

6.1 换个问法：最大岛屿面积

如果把H.Maze的查询去掉，改成“输出整个网格中最大的空白连通块大小”，那就是经典的最大岛屿面积题。LeetCode上有一堆类似题，本质都是Flood Fill。再扩展一点，如果把上下左右四个方向改成八个方向，也就是允许斜着连通，那只需要在方向数组里多放四个对角方向即可。

方向数组可以说是一招鲜吃遍天：

• 上下左右四方向：[(-1,0),(1,0),(0,-1),(0,1)]
• 八方向：再多加[(-1,-1),(-1,1),(1,-1),(1,1)]

很多网格搜索题，核心就是枚举方向数组，只要这个写对了，剩下的就是套模板。

6.2 动态墙变化：连通块问题的进阶形态

如果题目改成这样：初始有一个0/1网格，接下来有若干操作，有些操作是把某个格子从0改成1（砌墙），有些操作是查询当前最大连通块大小。这时候静态预处理就不够用了，因为每次改墙都会导致连通块分裂。这类题需要更高级的离线处理思路：把操作顺序反过来，从最终状态往前倒推，把“砌墙”变成“拆墙”，这样就能用并查集从后往前合并连通块，每次拆墙相当于合并两个集合。

这种“时间倒流”的思路在竞赛里叫离线逆向处理，是动态连通性问题的常用套路。理解了H.Maze的静态连通块查询，再往这个方向走就顺理成章了。

6.3 数据规模变化时的方案选型参考

我根据自己的做题经验，整理了下面这张选型表，遇到类似题可以直接参考：

多数校内赛和省赛的题目数据规模都落在前两行，所以Flood Fill预处理已经足够应对绝大部分场景。

7. 最后再分享一点实际操作上的经验

做题时有一个习惯对我帮助很大：在动手写正解之前，先写一个只针对小网格的暴力版，把样例手动跑一遍。这个过程能确保你完全理解了题意，而不是拿着半懂不懂的理解去写代码。样例过了不代表AC，但样例都过不了一定哪里理解偏了。

输出格式也是容易被扣分的地方。有的题要求每个查询结果一行，有的要求空格分隔，有的要求最后不能有多余的空行。我这次用的是字符串join，每个答案一行，简洁也不会多出多余空格。如果你不确定题目格式，优先采用“每行一个结果”，这几乎是最通用的约定。

关于要不要背模板，我的看法是：网上现成的Flood Fill模板很多，但直接复制粘贴容易忽略题目特有的边界条件。自己亲手完整实现一遍，比背十遍模板都管用。你会在实现过程中真正理解visited数组为什么必须在入队时标记、方向数组的坐标为什么这样写、block_size为什么要留一个下标为0的位置不用。

回到哈尔滨理工大学这道H.Maze，它整体难度适中，考点也很典型，没有刻意刁难人的地方，但对基本功的要求是实打实的。如果你能把BFS预处理、连通块编号、O(1)查询这三步走顺，这道题拿满分很稳。希望这篇复盘能帮到正在刷网格题的读者，尤其是刚开始接触Flood Fill的同学。动手写一遍，比盯着题解看十遍有意义得多。