题解

思路

把每一行和每一列各看成一个点。

做法

四周的墙使第一行、最后一行、第一列和最后一列天然属于同一个连通块；每个地面格 $(r,c)$ 又使第 $r$ 行与第 $c$ 列等价，因为能在其中一者停下当且仅当能在另一者停下。于是从 $(1,1)$ 出发能停到某一行或列，恰好对应它的点与边界连通块相连。滑冰场能够经过所有方格，当且仅当所有行都可停到，或所有列都可停到；而从任意起点都能先借助墙壁到达 $(1,1)$，所以这也正是题目的要求。

用并查集合并四个边界点，并对每个 # 合并对应的行点和列点。设含有行点的不同连通块有 $R$ 个，含有列点的不同连通块有 $C$ 个。把所有行连通至少要补 $R-1$ 条边，把所有列连通至少要补 $C-1$ 条边，而任意补边都对应把一个冰面格改成地面，因此答案为 $\min(R-1,C-1)$。

复杂度

扫描网格并合并即可，时间复杂度为 $O(HW\alpha(H+W))$，空间复杂度为 $O(H+W)$。