Codeforces Round #602 (Div. 1, based on Technocup 2020 Elimination Round 3) - C. Arson In Berland Forest
解説
問題文に与えられた入力をそのまま扱うのはちょっとやりにくいので、.でまずは囲ってしまいましょう。
そうすると、この問題は明らかに単調性があるので二分探索で解けます。
秒で可能かどうかを判定できれば、後はこの問題はとけました。
判定方法ですが、.からの縦と横が
以下のところは
Xとできません。(Xならば.が秒後に
Xになるからです)
Xにできない場所を2次元imos法などで求めましょう。
Xにできる箇所のうち、最終的に燃えてる箇所を全部Xとしても、.が燃やされることはないので問題ありません。
このときに、秒後の燃え方が入力で与えられた燃え方と同じであれば、
秒で可能ということが言えました！
