AGC033-A "Darker and Darker"

提出コード

考察

イメージとしては，既にある黒いマスから四方にどんどん黒いマスが広がっていくかんじです．

これにはキューを使ったBFSがよさそうです．

まずは，初期段階で黒いマスを全てキューにpushします．

キューの先頭要素に対して4近傍を見て，それが与えられたマスの外でなければキューにpushします．ただし，既に見たマスをキューに入れると同じ処理を永遠に繰り返すことになるので，各マスについて既に訪問したかを持っておく配列を作るといいでしょう．

また，問題文の1回の操作でどこまで黒いマスを広げられるかということが大事です．例えば，マス(2, 3)の右側(2, 4)を黒く塗ったとします．そして(2, 4)の右側(2, 5)も黒く塗ると，これは2回操作をしていることになります．

これを解決するには，各操作の初めにキューの大きさを見ておいて，その回数だけキューの先頭要素を見ていけばOKです．もちろんキューには後ろからどんどん次の探索点が追加されていきますが，操作初めのキューの大きさだけ見ることで，その操作でpushした点を見ることはないです．(次の操作で見ることになります．)

イメージ図は以下です．

f:id:chankilu23:20210217170315j:plain