网格连通块查询：Flood Fill预处理与BFS优化

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原因有三个思路线性不需要理解并查集的路径压缩和按大小合并。可以顺便把每个格子所属的块编号记录下来查询时直接索引非常直白。遍历顺序和地图方向数组的结合很自然不容易漏边界。当然如果你对并查集非常熟练用并查集也完全没问题。我见过很多高水平选手喜欢用并查集因为这类题的查询点有时比较复杂并查集处理“临时拆墙”类变种时更灵活。最终选型看个人熟练度没有绝对的对错。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.stdoutPython的内置input()和print()在数据量大时性能很差。q到10万级别print逐行输出会带来大量I/O开销直接TLE。用sys.stdin.readline读行、用sys.stdout.write一次性输出是竞赛Python选手的基础操作。用deque而不是listBFS的队列弹出如果用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(nmq)空间复杂度O(nm)。n*m如果达到100万级别需要大约三个二维整型数组每个数组在C里约4MBPython里的内存开销会大不少但一般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不要急着怀疑算法整体先检查几个常见的性能陷阱可疑点检查方式常用解决方案输入输出方式是否用了print逐行输出改用sys.stdout.write汇总输出队列类型是否用list.pop(0)改用collections.deque递归深度是否用DFS递归改BFS迭代写法重复计算是否在循环内重复创建大对象提出来复用顺带一提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 数据规模变化时的方案选型参考我根据自己的做题经验整理了下面这张选型表遇到类似题可以直接参考数据规模推荐方案理由n*m ≤ 10^4q ≤ 10^3朴素BFS数据小怎么写都行n*m ≤ 10^6q ≤ 10^5Flood Fill预处理时间O(n*mq)空间可控n*m ≤ 10^7q ≤ 10^6Flood Fill 一维数组压缩减少二维list的内存开销带墙动态变化离线逆向并查集从最终状态反向合并多数校内赛和省赛的题目数据规模都落在前两行所以Flood Fill预处理已经足够应对绝大部分场景。7. 最后再分享一点实际操作上的经验做题时有一个习惯对我帮助很大在动手写正解之前先写一个只针对小网格的暴力版把样例手动跑一遍。这个过程能确保你完全理解了题意而不是拿着半懂不懂的理解去写代码。样例过了不代表AC但样例都过不了一定哪里理解偏了。输出格式也是容易被扣分的地方。有的题要求每个查询结果一行有的要求空格分隔有的要求最后不能有多余的空行。我这次用的是字符串join每个答案一行简洁也不会多出多余空格。如果你不确定题目格式优先采用“每行一个结果”这几乎是最通用的约定。关于要不要背模板我的看法是网上现成的Flood Fill模板很多但直接复制粘贴容易忽略题目特有的边界条件。自己亲手完整实现一遍比背十遍模板都管用。你会在实现过程中真正理解visited数组为什么必须在入队时标记、方向数组的坐标为什么这样写、block_size为什么要留一个下标为0的位置不用。回到哈尔滨理工大学这道H.Maze它整体难度适中考点也很典型没有刻意刁难人的地方但对基本功的要求是实打实的。如果你能把BFS预处理、连通块编号、O(1)查询这三步走顺这道题拿满分很稳。希望这篇复盘能帮到正在刷网格题的读者尤其是刚开始接触Flood Fill的同学。动手写一遍比盯着题解看十遍有意义得多。