Surrounding Area 解説
- 問題名：Surrounding Area [土地囲い]
- 出典：Problem C, ACM/ICPC Practice Contest for Japan Domestic, 2007-06-24
- 難易度：☆☆
- 問題の種類：再帰
- 解法：領域の塗りつぶし
- 解答ソースコード：
- OB/OGの会の解説：p0106-obog.pdf
アルゴリズムの概略
この問題は，2004年度愛媛大会の国内予選のB問題「Red and Black」の発展系の問題です。 発展系とはいっても難易度はほぼ同等の問題で，解法も同様に領域の塗りつぶしでOKで，再帰関数を書くと簡単に解けます。
注意点としては，
- 全ての B と W から再帰関数を呼び出す必要があること
- BとWの色はそれぞれ別に色付けすること（解答ソースコードではBのときb，Wのときwにしています）
- 一度他の色で訪れていても，別の色では訪れて再帰関数を適用しなければならない＝2色塗られる場合があること（解答ソースコードではoにしています）
が挙げられます。
その他，基本的なことは「Red and Black」の解説を参照してください。
アルゴリズムの計算量
一度処理したマス目は同じ色ではもう二度と処理しないので， フィールドのサイズ n = w×h×（色数） 回再帰関数を適用すると解け，計算量は O(n) になります。
$Id: index.shtml 1576 2007-06-25 15:10:28Z SYSTEM $