01-矩阵联通

算法思路

使用广度优先搜索（BFS）判断所有值为 $1$ 的单元格是否属于同一个连通块。

首先扫描矩阵，统计值为 $1$ 的单元格总数 $S$，并记录其中任意一个作为搜索起点。如果 $S=0$，根据题意直接输出 No。

否则，从起点开始 BFS。每次只向上、下、左、右四个方向扩展，且目标位置必须在矩阵内、值为 $1$、尚未访问。单元格入队时立即标记，避免重复入队。

统计搜索访问的单元格数量 $C$，其中包括起点。若 $C=S$，说明所有的 $1$ 均可从起点到达，输出 Yes；否则输出 No。

正确性证明

BFS 只经过相邻且值为 $1$ 的单元格，因此访问到的所有单元格都与起点连通。同时，BFS 会遍历所有可以从起点到达的单元格，所以访问范围恰好是起点所在的连通块。

当 $S>0$ 时，$C=S$ 表示所有值为 $1$ 的单元格都在该连通块内；$C<S$ 表示存在无法从起点到达的 $1$。当 $S=0$ 时，算法按题意输出 No。因此算法正确。

复杂度分析

扫描矩阵需要 $O(nm)$ 时间。每个单元格至多入队一次，每次检查四个方向，因此每个测试用例的时间复杂度为 $O(nm)$，所有测试用例的总时间复杂度为 $O(\sum nm)$。

存储矩阵、访问标记和搜索队列需要 $O(nm)$ 空间。