AtCoder Regular Contest 131 B 問題 Grid Repainting 4
問題
提出解答
問題の概要
行
列マスからなるマスがある. この
個のマスそれぞれに対して, 色
のいずれかで彩色する. ただし, 上下左右に隣り合うマス同士は同じ色で塗ってはいけない.
いくつかのマスで塗る色が決まっている時, 条件を満たすような彩色を1つ挙げよ.
制約
- 彩色が決まっていないマスが存在する.
- 可能な彩色が存在する.
解法
制約から, すでに決まっている彩色に矛盾が発生していないので, 以下のようにして条件を満たす彩色を求めることができる.
- 彩色が決まっていないマス全体の集合を
とする.
- 各
に対して, 以下を実行する.
の上下左右を見て, 可能な色を見つけ (色の候補は5個で, 隣接するマスは高々4個なので, 必ず可能な色は存在する), その色で塗る.
- 彩色を出力する.
このような愚直なアルゴリズムで計算量 で彩色を見つけることができる.
