AtCoder AGC 033 A - Darker and Darker (図解、Ruby実装例)
問題概要
H × W の盤面があり、各マスは「白(.)」「黒(#)」に塗られている。1 秒ごとに、各黒マスの上下左右に隣接している白マスを黒く塗る。全マスが黒になるのに何秒要するかを求めよ。
例
2秒後に全マスが黒くなるため、答えは2秒。
方針
- 盤面を全探索して、黒マスの上下左右に白マスがあれば黒く塗る作業を繰り返す
- 全ての白マスについて、最寄りの黒マスまでの距離を調べる
などの方法はTLEが予想されるため、
- 黒マスの座標をキューに格納し、上下左右を黒く塗る作業を繰り返す
という方針とします。（幅優先探索）
また、黒く塗るのに要した秒数を管理するため、
- 白マスは -1 （未探索）
- 黒マスは黒く塗るのに要した秒数
とする、数字バージョンの盤面を操作します。
図解
3秒後に黒塗りしたマスは存在しないため、答えは2秒。
Ruby実装例（コメント付き）
Submission #5998528 - AtCoder Grand Contest 033
存在しない盤面の枠外を黒塗りしないように、if文の条件には注意が必要です。
感想
コンテスト中はACを出せませんでしたが、何とか他の方のコード例を解読することができたため、実装して図解多めで記事を書いてみました。
今回は、
- 同じマスを繰り返しチェックしないように、黒マスの座標を格納する配列を用いたこと
- 若い秒数から塗りつぶしていくために、配列（キュー）を用いた幅優先探索を用いたこと
がポイントとなりました。幅優先探索を効果的に使えたのは初めてだったため、なかなか面白かったです。
参考
キューはshift、スタックはpopを使って操作します。
