第11回日本情報オリンピック 予選5

2011年12月23日
情報オリンピック日本委員会

問題
   イルミネーション (Illumination)

解説

地図の外側に余白を設け余白とそれに隣接している建物のない領域をペイントツールの塗りつぶしツールと同じ要領で下図のように塗りつぶす.塗りつぶした結果,塗りつぶした領域と建物のある領域の境界の長さが答えとなる.

今回の問題では塗りつぶす領域の大きさは小さいので塗りつぶしは再帰を用いて隣接する領域を塗りつぶすことができる.しかし,再帰を用いて大きな領域を塗りつぶす場合は,スタックメモリが溢れないように幅優先探索を用いて塗りつぶしを行わなければならない.