きままにものづくり

日々の気付いたことなんかを書いてます。

SRM593Div1Easy

問題

N*Nの配列が与られる。各マスは六面体となっており、要素はXか-である。Xの箇所を任意の色で塗りたい。ただし、隣り合うマスでは違う色とする。この時に必要な色の最小数を求めよ。

解法

3色あればどんな場合でも塗ることができる。なので、0、1、2のどれであるかを調べることで答えが求まる。Xがない場合は0、Xが隣合ってない場合は1となる。一つの要素としか隣合っていない場合は2となる。深さ優先探索を行うことで答えは求まる。

計算量

 O(N^2)

コード