[AtCoder] AISing Programming Contest 2019 C – Alternating Path

2019年6月9日

問題

方針

各マスに番号を割り振る

\( H \) 行 \( W \) 列のマスを持つグリッドにおける \( i \) 行 \( j \) 列目のマスの番号を \( i \times W + j \) とします。このようにマスの番号を割り当てると \( 0 \) から \( HW – 1 \) までの範囲で一意に番号を持ちます。

パスの数を求める (深さ優先探索)

黒マスから白マスへのパスの数の合計を求めます。ただし、パスは黒白黒白黒…と交互に色が変わるパスとします。
ある黒マス \( B_i(x_i, y_i)\) を始点として、到達できる白マスと黒マスの数 \( w_i, b_i \) を求めます。このとき、始点の黒マスもカウントします。到達できるマスは全て連結されているので、任意の黒マスから任意の白マスへのパスが存在します。したがって、この連結において求めるパスの合計は \( w_ib_i \) となります。

パスの数を求める (Union Find)

ある要素がどのグループに属すかといった問題では、Union Find を使うことができます。Union Find については、下の記事がまとまっていると思います。

あるパスにおける白マスと黒マスの個数が分かればよいでの、Union Find を使ってそれらを求めます。

コード

提出したコード (深さ優先探索)

提出したコード (Union Find)

Union Find