黑白纸片连通块问题解析：DFS、BFS与并查集三种解法对比

面试题这个东西最怕的就是“背答案”。尤其是春招这种节奏快、考察覆盖面广的场景刷题的意义不在于记住某道题的解法而在于通过一道题把一类题的底层逻辑打通。“黑白纸片”这类题目听起来像是拼图游戏或者剪纸质感的趣味题实际上落到代码里就是非常经典的连通块计数问题跟LeetCode上的岛屿数量、图像渲染、省份数量是同一棵树上的果子。这次顺丰春招卷子里的第二题把它换了个包装用纸片当壳考的还是DFS、BFS和并查集那套基本功。我用了Java、C和Python三种语言分别过了一遍配合在线OJ测试整理出了这份完整解析从题意拆解到每种语言的实现细节再到容易踩的坑一次性说清楚。这道题适合三类人看正在准备春招、需要把连通块问题吃透的应届生想对比三种主流语言在同一道算法题上写法的差异、顺便复习STL和标准库用法的开发者以及想把“会做题”升级成“会讲题”的面试准备者。1. 题目理解与整体思路拆解1.1 题目到底在问什么先还原一下题目的原始描述。有一张由黑白格子组成的矩形纸片被分成了M行N列的网格每个格子上要么是黑色要么是白色。相邻的定义是两个格子有公共边即上下左右四个方向斜对角不算。现在需要统计这张纸片上一共有多少块“黑色纸片”——所谓一块黑色纸片就是由若干个相邻的黑色格子组成的整体白色格子会把它们隔开。这就是标准的连通块计数。输入格式通常是第一行两个整数M和N表示行数和列数接下来M行每行给出N个整数0代表白色1代表黑色。输出是一个整数代表黑色连通块的数量。有些版本会稍微改一改比如用字符矩阵或者把方向定义成八个方向、允许斜着相连但核心逻辑不变。这类题的精髓在于“连通”这个词。用一个生活化的类比你往黑色格子的区域倒一桶水水会沿着相邻的黑色格子流遍整个连通区域但遇到白色格子就停下来。倒一桶水覆盖到的所有黑色格子就是一块纸片倒了几桶水就说明有几块纸片。这个“倒水”的动作翻译成算法语言就是搜索。1.2 为什么面试官喜欢拿它当春招题春招笔试不同于社招的深度考察它更像是一张过滤网。时间有限、题量固定每道题都要在十几分钟内考察出候选人的多项素质。黑白纸片这道题能出现在顺丰的春招卷里恰恰是因为它在多个维度上都合格第一模型转换的思维。题面用“纸片”包装本质上考察的是能不能快速把实际问题抽象成图论模型。面试官想看的是你拿到一道生活化题目时是直接懵掉还是能马上意识到“这不就是矩阵上的连通性判断吗”。第二基础算法的熟练度。DFS、BFS、并查集是数据结构和算法里的基本功任何一个岗位用到这些都不奇怪。三道题里如果有一道是纯考堆砌复杂数据结构的偏题那对大多数人是无效的连通块这种难度适中、解法多样的题反而能拉开区分度。第三代码实现的规范性。这道题的边界判断、数组越界、访问标记、递归深度控制每一处细节都藏着扣分点。能在规定时间内把代码写干净、不犯低级错误本身就是一种能力证明。所以别小看这道“简单题”它是一面照妖镜基础扎不扎实一照便知。1.3 整体算法框架遍历 搜索解决连通块计数的通用框架非常统一三步走从左上角开始逐行逐列扫描整个矩阵。遇到一个“未访问过的黑色格子”时答案计数器加一然后从这个格子出发做一次完整的搜索把和它连通的所有黑色格子全部标记为已访问。扫描继续直到遍历完整个矩阵输出计数结果。这里的核心在于第二步的“搜索”。可以用**深度优先搜索DFS递归地往四个方向钻进黑色区域也可以用广度优先搜索BFS借助队列层层往外扩还可以用并查集Union-Find**先把所有黑色格子的相邻关系全部合并一遍最后数一数有多少个独立的集合。三种思路在时间复杂度上都是O(M×N)因为每个格子最多被访问一次。空间复杂度上DFS最坏情况下递归层级就是连通块的大小极端情况整个矩阵全黑下递归深度可能达到M×N所以Python里需要手动调大递归限制这属于典型的“大坑”BFS的空间取决于队列的最大长度也就是一层里最宽的数量一般不会超过矩阵的短边长度并查集则需要额外开一个大小为M×N的父节点数组。具体场景下的选择逻辑后面第二章展开细说。2. 核心算法原理详解三种主流方案怎么选2.1 DFS最直观的递归染色DFS的思路和“倒水”这个比喻几乎一模一样。从起点格子出发标记为已访问然后依次探测上、下、左、右四个邻居如果邻居是黑色且没被访问过就递归进入这个邻居继续同样的动作。用代码伪表达一遍主流程计数 0 对于矩阵中每一个位置(i, j): 如果 grid[i][j] 黑色 且 未访问: 计数 1 DFS(i, j)DFS函数本身要做什么DFS(x, y): 标记 (x, y) 为已访问 对于每个方向 (dx, dy): 计算新坐标 nx x dx, ny y dy 如果 nx、ny 在矩阵范围内 且 grid[nx][ny] 黑色 且 未访问: DFS(nx, ny)DFS最大的优势是写起来爽代码量最小逻辑直白和人对“一块纸片”的直觉完全一致。它的代价是递归深度受限。面试现场如果矩阵规模没给明或者明确说M和N可以到1000以上就要考虑递归栈溢出的风险。这时候要么在开头主动调大递归限制要么直接换成BFS或迭代式DFS自己维护一个栈。2.2 BFS没有递归栈风险的遍历方式BFS把递归换成了队列思路变成了“从起点出发先看看四周有哪些邻居能走把它们全部放进队列然后一个一个处理”。主流程几乎一样只是搜索函数内部变成了循环结构BFS(startX, startY): 创建队列 把(startX, startY)入队并标记为已访问 当队列非空: 弹出队头元素 (x, y) 对于每个方向: 计算邻居坐标 如果邻居合法 且 是黑色 且 未访问: 标记邻居已访问 邻居入队值得注意的是这里“标记已访问”的动作必须发生在入队的那一刻而不是出队的时候。如果等到出队再标记同一个格子可能被多个邻居重复入队虽然最终结果不会错但队列里会有大量冗余元素最坏情况下空间和时间都会被白白浪费。这是我实际写代码时踩过的坑后面第五章会再提。BFS的优势是不用担心递归深度适合矩阵特别大的情况。代价是手写的队列操作比递归稍微繁琐一点在Java和C里通常用ArrayDeque和queuepairint,int来解决Python里则直接用collections.deque来保持双向队列的高效入队出队。2.3 并查集另一种视角的连通性统计DFS和BFS是“从起点开始往外扩”并查集则是一种完全不同的思路它不主动“搜索”而是把所有黑色格子之间相邻关系逐条“合并”。最后数一下有多少个集合每个集合代表一块纸片。并查集的核心操作有两个find(x)找到x所在集合的代表元素根节点同时做路径压缩。union(a, b)把a和b所在的两个集合合并成一个。对于这道题做法是先把整个二维矩阵铺平成一维也就是给每个格子编号idx i * n j然后扫描每个黑色格子看它的右方邻居和下方邻居是否也是黑色如果是就把这两个格子合并。为什么只需要看右和下因为合并关系是双向的看左上已经覆盖看右和下就能覆盖所有相邻关系。合并结束后把所有黑色格子找一遍根不同的根的数量就是答案。这里其实还能优化直接在合并过程中用变量统计“当前独立的集合数量”初始化时每个黑色格子自成一个集合每次合并成功就减一省去最后再遍历一遍。并查集的代码量在三种方案里最大但它有一个其他方案没有的优势不用死记方向数组对“八连通”甚至“任意不规则连通规则”的扩展特别自然。如果题目要求你计算黑色纸片里最大的一块面积DFS和BFS都能做但并查集要额外维护集合大小信息也不复杂。2.4 三种方案的对比与取舍方案核心数据结构时间复杂度空间复杂度代码量风险点DFS系统递归栈O(M×N)O(最坏连通块大小)最少递归过深导致栈溢出BFS显式队列O(M×N)O(队列最大宽度)中等重复入队导致冗余并查集父节点数组O(M×N×α)O(M×N)较大坐标压缩时容易下标搞错这里的α是反阿克曼函数在实践中可以认为是一个不超过5的极小常数所以并查集的时间复杂度也维持在近乎线性的水平。实际做题时怎么选我个人的习惯是矩阵规模不超过200×200时首选DFS写起来最快不容易出逻辑错误规模接近1000×1000甚至更大时果断上BFS稳字当头如果题目还附带多个查询、动态合并之类的附加条件直接考虑并查集它天然支持动态连通性判断这是DFS和BFS做不到的。3. 三种语言的完整代码实现3.1 Java版面向对象风格与递归DFSJava在春招笔试里最常见的写法就是递归DFS版本配合Scanner处理标准输入。关键点有几个方向数组要定义成静态二维数组递归出口的判断要写在访问邻居之前visited数组用boolean[][]默认值就是false省事。import java.util.*; public class Main { private static final int[][] DIRS {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); int n sc.nextInt(); int[][] grid new int[m][n]; for (int i 0; i m; i) { for (int j 0; j n; j) { grid[i][j] sc.nextInt(); } } boolean[][] visited new boolean[m][n]; int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1 !visited[i][j]) { count; dfs(grid, visited, i, j); } } } System.out.println(count); } private static void dfs(int[][] grid, boolean[][] visited, int x, int y) { visited[x][y] true; for (int[] d : DIRS) { int nx x d[0]; int ny y d[1]; if (nx 0 nx grid.length ny 0 ny grid[0].length grid[nx][ny] 1 !visited[nx][ny]) { dfs(grid, visited, nx, ny); } } } }这段代码里有一个细节值得展开nx 0 nx grid.length和ny 0 ny grid[0].length这四个条件是先判断是否越界再访问数组元素。Java和C里都遵循从左到右的短路求值如果越界条件在前且为真后面的数组访问根本不会执行所以安全。如果顺序反过来先读grid[nx][ny]再判断边界一旦越界就会抛ArrayIndexOutOfBoundsException这是新手最容易翻车的地方。3.2 C版STL容器与BFS队列C在这个场景下最大的优势是STL容器足够好用。vectorvectorint存矩阵vectorvectorbool存访问标记queuepairint,int作为BFS队列。cin读取标准输入时虽然比scanf稍微慢一点但在笔试环境通常够用除非明确了超大数据量那可以考虑关闭同步锁加速也就是在main里写一行ios::sync_with_stdio(false);。#include bits/stdc.h using namespace std; const int DIRS[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m, n; cin m n; vectorvectorint grid(m, vectorint(n)); for (int i 0; i m; i) { for (int j 0; j n; j) { cin grid[i][j]; } } vectorvectorbool visited(m, vectorbool(n, false)); int count 0; queuepairint, int q; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1 !visited[i][j]) { count; q.push({i, j}); visited[i][j] true; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (auto d : DIRS) { int nx x d[0]; int ny y d[1]; if (nx 0 nx m ny 0 ny n grid[nx][ny] 1 !visited[nx][ny]) { visited[nx][ny] true; q.push({nx, ny}); } } } } } } cout count endl; return 0; }C版本的BFS里auto [x, y]是C17的结构化绑定特性能直接从pair里拆出两个变量比用q.front().first和q.front().second直观得多。如果你的本地编译环境没开C17这套代码在在线OJ上也能跑因为大多数在线OJ的默认标准已经是C17。如果确实遇到老编译器改成显式取first、second就行。3.3 Python版简洁实现与递归深度调整Python的代码几乎和伪代码一样清晰但有两个必须注意的坑一是递归深度默认只有1000如果矩阵很大且全是黑色DFS会直接崩在RecursionError上所以要么sys.setrecursionlimit()调大上限要么直接用BFS。二是sys.stdin.read().split()一次性读入所有数据的写法在笔试里会显著提升输入效率比input().split()逐行读要稳而且代码更短。import sys from collections import deque DIRS [(-1, 0), (1, 0), (0, -1), (0, 1)] def solve(): data sys.stdin.buffer.read().split() if not data: return idx 0 m int(data[idx]) n int(data[idx 1]) idx 2 grid [] for _ in range(m): row list(map(int, data[idx:idx n])) idx n grid.append(row) visited [[False] * n for _ in range(m)] count 0 for i in range(m): for j in range(n): if grid[i][j] 1 and not visited[i][j]: count 1 q deque() q.append((i, j)) visited[i][j] True while q: x, y q.popleft() for dx, dy in DIRS: nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] 1 and not visited[nx][ny]: visited[nx][ny] True q.append((nx, ny)) print(count) if __name__ __main__: solve()Python的deque.popleft()是O(1)的操作如果用list.pop(0)来模拟队列每次弹出都会把整个列表往前挪一位总复杂度会退化成O(M×N×短边长度)在大矩阵上会慢到离谱。这在网上能搜到不少反面案例都是用list硬扛BFS然后超时的。所以我不厌其烦地再次强调Python里写BFS队列一律用collections.deque。4. 在线测试与样例验证4.1 测试用例怎么设计在线OJ测试遵循一个基本逻辑样例过了不代表代码对了样例没过那说明代码肯定有问题。真正的可靠性来自自己额外补充的边界用例。我来分享几个我实测时一定会加进去的用例。第一个是最小规模1 1矩阵只有一个格子。如果它是黑色答案应该是1如果是白色答案应该是0。这个用例能直接验证主循环是否正常执行也能避免那种“运行起来连输入都读不对”的低级问题。第二个是全黑矩阵比如3 3全部是1。答案是1整个矩阵就是一块纸片。这个用例能验证搜索是否能覆盖所有方向也在极限上考验了DFS的递归深度。第三个是全白矩阵答案必须是0。有些人会在主循环里写if (grid[i][j] 1)判断全白矩阵没问题但如果你没有判断颜色就进来搜索就会把白色也算成一块这是低级失误。第四个是棋盘交错黑白相间、类似国际象棋棋盘。这种矩阵中没有任何两个黑色格子是相邻的所以黑色纸片数量等于黑色格子数量本身。这个用例能验证方向数组是否准确尤其是会不会把斜对角错误地当成相邻。下面用一个具体的样例走一遍输入 4 5 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 0 0 1 输出 4因为左上角两块连成一块右上角两块连成一块第二行第三列和第三行第三列再加第三行第四列又连成一块最后角落里单独一个再加一个单独一个总共4块。用这段样例跑三种语言版本输出一致可以初步确认代码逻辑。4.2 不同OJ上的细节差异在线测试时不同平台在输入输出上会有一些微妙的差别。有的OJ是多组测试数据读入到一个EOF才结束代码就要包一层while(sc.hasNext())或while(cin m n)有的是单组测试输入格式固定直接读即可。标题里提到的在线测试大部分情况下都是单组输入但我建议在本地练习时把多组版本的写法也准备好因为很多时候你放到题库里调试后台数据就是多组的少写一层循环就会少得很多分。输出端的细节也值得提一句换行符是标准答案的一部分print(count)默认带换行Java的System.out.println也带C的cout count endl也带。如果你习惯用System.out.print(count)或者cout count在某些严格比对输出结果的OJ上会被判成Presentation Error这属于非技术原因丢分非常可惜。另外一个本地调试小技巧如果你是用在线OJ提交先在本地写好带样例的测试脚本跑通之后再删掉测试代码只保留核心逻辑上传。比起直接在网页里盲改代码这个流程能帮你节省大量时间。5. 常见问题与实战避坑5.1 递归深度造成的栈溢出这是DFS方案最大的坑。Java里每个线程有一个固定的栈大小递归层级太深会抛出StackOverflowErrorPython里默认递归限制是1000层超出后直接RecursionError。我印象最深刻的一次是拿一个2000×2000的全黑矩阵去测递归版DFSJava和Python双双击穿那一刻才真正理解BFS存在的意义。针对这个问题的解法有三个层次如果矩阵规模已知较小放心用递归DFS调通即可。如果矩阵规模可能较大直接用BFS根本不给栈溢出的机会。如果想坚持DFS可以手写一个显式栈来模拟递归本质上是把系统栈换成堆内存里的栈矩阵再大也不会栈溢出代价是代码复杂一点。顺带一提在面试中如果你的解法能主动说出“我考虑过DFS的栈溢出风险所以选择了BFS”这是一个隐藏的加分项因为它代表着你不仅会写代码还懂得权衡工程风险。5.2 边界判断顺序的经典失误再强调一次数组访问越界判断必须放在访问之前。C、Java、Python这几种语言在这一点上的行为不同Java越界直接抛异常C的越界是未定义行为可能程序崩了也可能没崩但结果是错的Python会抛IndexError。不管是哪种语言正确的写法永远是先把越界条件写在前面。一个好的习惯是把边界判断封装成一个独立的isValid(x, y, m, n)函数或者用一个统一的if条件让代码的可读性和安全性兼得。别小看这个细节笔试环境下时间一紧张这部分错误是最高发的一类。5.3 多语言工程实现的性能差异同样一道题三种语言放在同一台机器上跑速度差距是肉眼可见的。C通常是最快的Java次之Python如果不加优化会慢不少。但这是语言特性决定的不公平竞赛笔试环境不会要求你用Python跑上千万级的矩阵规模所以不要有“Python太慢所以不配刷题”的错觉。Python代码的性能优化优先级我总结一下首选sys.stdin.buffer.read()读取数据次选collections.deque做BFS队列再次避免在循环内做列表推导式。这三点做到了Python版本的黑白纸片在常规测试数据下都能跑进一两秒。C优化的重点则是ios::sync_with_stdio(false)和cin.tie(nullptr)这两行能极大降低读写开销。Java在笔试场景下的性能想再进一步可以用BufferedReader替换Scanner不过黑白纸片这题的数据量通常不大Scanner足够。5.4 答案统计的隐蔽逻辑错误把“统计黑色纸片数量”误写成了“统计黑色格子的数量”这是另一种常见错误。前者是在扫描主循环里遇到黑色格子才加一而且加一的前提是它没有被任何一次搜索访问过后者是只要看到1就加一。从字面上看两者很像但结果差异巨大。要区分清楚最好的办法就是在写完代码后手动跑一遍样例对照标准输出再额外加上“全黑矩阵”这个用例一眼就能看出来逻辑是不是对的。5.5 矩阵坐标压缩时的下标错误用并查集方案时二维坐标(i,j)到一维下标id的映射是id i * n j。这里最常犯的错误是把它写成i * m j这种错误在矩阵行列数不相等的时候表现特别隐蔽程序不报错也没有越界异常就是答案不对。排查起来也困难因为你只会在整个矩阵扫描完毕后发现返回值偏少或偏多很难直接定位到是哪一行出了问题。怎么预防把矩阵第0行的格子编号在草稿纸上演算一遍确认0到n-1第1行从n开始所有行的编号能连续覆盖到m×n-1这个映射就没问题了。提示在代码中用id i * n j固定写法时可以额外加一个if (id ! i * n j)的断言自检虽然不影响最终答案但在调试阶段能救命。写在最后这一题背后的面试观黑白纸片这道题现在看来简单但它背后藏着的面试逻辑是我最想分享的。春招笔试不是竞赛它更看重的是“稳定发挥”也就是在有限时间内把一个中等难度的基础题做对、做稳、做干净。比如这道题如果能在10分钟内写出DFS或BFS版本并且考虑到了矩阵边界、访问标记、极端用例那么这道题对你来说就是一道好题它帮你建立起来的是“拿到任何连通性问题都可以套搜索框架”的底气。我个人在实际操作中反复练过三种语言写同一个题最大的收益不是多会了几种语法而是能直观感觉到每种语言在设计上的取舍Java的工程严谨、C的底层自由、Python的表达简洁各有各的侧重点。后续如果想把这个题目继续扩展可以试试用这道题来练习“求最大黑色纸片面积”“求每个黑色纸片的周长”或者“判断两块纸片是否通过一个格子就能连接”这些变体题目都能在黑白纸片的基础上无缝迁移一通百通。