AGC033 A - Darker and Darker

問題
提出コード

解法

マスが黒になるのは、初期状態における黒いマスとのマンハッタン距離を全て調べ、そのうちの最小値回だけ操作を行ったときになります。
ので、全てのマスについて、初期状態に存在している黒いマスとのマンハッタン距離の最小値を調べ、その中で最も大きいものを選べばよいです。
が、愚直にこれを計算すると間に合わないので、工夫する必要があります。
あるマスと別のマスにおけるマンハッタン距離は、4方向にBFSした際の手数と同じになります。
距離を求めるために黒いマスからBFSすることを考えると、最初に、キューに黒いマスを全て放り込み、そこからまだたどり着いていないマスへBFSを行うことで、黒いマスと全てのマスとの最短距離が求まります。
あとは、求まった距離の最大値を求めればよいです。

感想

これを5分ほどでバグなく書くことができたのはICPCのおかげ…でしょうか？
あんまりAGCっぽくないなと思いました。