Microsoft OA 面试真题解析：统计二值矩阵中的连通块

Count Connected Components in a Binary Matrix

Given a binary matrix, count the number of connected components formed by the cells with value 1. Cells are connected if they are adjacent vertically or horizontally.

For example:

1 0 1 0
0 0 2 0
0 0 0 0
0 0 0 0

and

2 0 0 1 0
0 0 0 0 0
0 2 0 0 1
0 0 0 0 0
1 0 2 0 0

这道题本质上是矩阵连通块统计：把满足条件的格子看作图中的节点，若上下左右相邻则连边，最后计算连通分量数量。典型做法是遍历整个矩阵，遇到未访问的目标格子时用 DFS 或 BFS 把整个连通块“淹没”并计数一次。实现时通常需要一个 visited 数组避免重复搜索，时间复杂度为 O(mn)，适合在 OA 和面试中快速完成。