[AtCoder] AISing Programming Contest 2019 C – Alternating Path

Alternating Path

割とよくあるアルゴリズムの問題だと思います。

考え方

題意

黒マスから白マスへのパスの数の合計を答えます。ただし、パスは黒白黒白黒…白と交互に色が変わるパスとします。

方針

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

次に、全てのパスを数え上げるために、全ての黒マスから深さ優先探索を行って、上記の計算を行います。このとき、\(B_i\) から到達した黒マスは始点として採用しません。また、深さ優先探索において効率的に探索するために、一度訪れたマスを記憶しておき、別の深さ優先探索で探索を行わないようにします。

以上より、全ての始点から出発してできる連結において、パスの合計を足し合わせたものが答えとなります。

コード

感想

本番では int と long の違いで WA となってしまいました。

それと、幅優先探索でも解けると思います。基本的には迷路を解くアルゴリズムと変わらない難易度だっただけに、もうちょっと慎重になれば良かったと思いました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする