原案: potetisensei

条件の言い換え

どのマスから始めてもマス \((1,1)\) の上で静止できるため、マス \((1,1)\) から見てスケートリンクに無駄がなければ、 どのマスから見てもスケートリンクに無駄がないということになります。 よって、マス \((1,1)\) の上で静止した状態から始めた場合を考えれば良いです。

マス \((1,1)\) から始めて、その行のいずれかのマスの上で静止できるような行を 良い行 と呼ぶことにします。 同様に、マス \((1,1)\) から始めて、その列のいずれかのマスの上で静止できるような列を 良い列 と呼ぶことにします。

以下の \(2\) 条件は同値です。

• (A) マス \((1,1)\) から見てスケートリンクに無駄がない。
• (B) すべての行が良い行である。または、すべての列が良い列である。

これを示します。まず、(B) ならば (A) を示します。 すべての行が良い行であるとします。 マス \((r,c)\) を任意にとります。すべての行が良い行であるため、\(r\) 行目で静止することができます。 その状態から東か西に移動を開始すれば、マス \((r,c)\) を通過することができるため、(A) が示せました。 すべての列が良い列である場合も同様です。

次に、(A) ならば (B) の対偶を示します。 \(r\) 行目のどのマスにも静止できないような \(r\) と、\(c\) 列目のどのマスにも静止できないような \(c\) があったとします。 壁のおかげで \(1\) 行目と \(1\) 列目には必ず静止できるため、\(r,c\) は \(1\) ではありません。 このとき、マス \((r,c)\) の上は絶対に通過できません。なぜなら、マス \((r,c)\) の上を通過するためには、 \(r\) 行目のどこかで静止したあとに（東か西に）移動を開始するか、\(c\) 列目のどこかで静止したあとに（北か南に）移動を開始する必要があるためです。

解法

壁のおかげで、次が成り立ちます。

• \(1\) 行目が良い行 \(\iff\) \(1\) 列目が良い列
• \(1\) 行目が良い行 \(\iff\) \(W\) 列目が良い列
• \(H\) 行目が良い行 \(\iff\) \(1\) 列目が良い列
• \(H\) 行目が良い行 \(\iff\) \(W\) 列目が良い列
• \(1\) 行目が良い行

また、マス \((r,c)\) が地面であるとき、次が成り立ちます。

• \(r\) 行目が良い行 \(\iff\) \(c\) 列目が良い列

各行と各列に対応する頂点を用意し、「\(r\) 行目が良い行 \(\iff\) \(j\) 列目が良い列」が成り立つような頂点間に辺を張ったグラフを 考えます。氷のマスを地面のマスに変更することは、このグラフに辺を追加することにあたります。

\(r\) 行目が良い列であることと、このグラフで\(r\) 行目に対応する頂点と \(1\) 行目に対応する頂点が連結であることは 同値です。つまり、このグラフの行に対応するすべての頂点が連結であることと、すべての行が良い行であることは同値になります。 よって、すべての行を良い行にするために必要な最小のマスの変更回数と、行に対応するすべての頂点を連結にするために追加するべき辺の最小本数は一致します。 行に対応するすべての頂点を連結にするために追加するべき辺の最小本数は、行に対応する頂点の連結成分の数から \(1\) を引くと求めることができます。 列についても同様です。

よって、答えは \(\min(\text{行に対応する頂点の連結成分の数}-1, \text{列に対応する頂点の連結成分の数}-1)\) です。 このような連結成分の数は深さ優先探索や幅優先探索によって \(O(HW)\) で求めることができるほか、 Disjoint set union を使っても求めることができます。

C++による実装例

Pythonによる実装例