QUPC2018-C:Ito Campus
慣れているとなんてことない問題だが,ちゃんと書いてみる。
解説
@から距離以内のマスは安全でないなので,そのようなマスを調べて安全でないマークをつけてから,安全なマスだけでSからGへの最短距離を調べればよい。安全でないマスを調べるのも,SからGへの最短距離を調べるのも,幅優先探索(以下bfs)すればよいのだが,前者については注意が必要という問題である。
例えば,「@を見つけたら,そこからbfsで距離X以内のマスに安全でないマークをつける」ということをすると,毎回のbfsにかかり,@がいっぱいあると計算量がとなり,TLEする。
では,「安全でないマークをつけたマスは壁'#'にしてしまう」というアイデアはどうか。これならば,同じマスを2度以上探索しないのでTLEは回避できる。しかし,これではWAを踏んでしまう。例えば,として,以下のような状況を考えてみよう。外側の壁は省略してある。
ここで,(1,1)にある@から探索をすると,以下のようになる。
これで,(3,1)からあるマスを探索しようとしても,イノシシは壁を通れないので,ここで安全でないマスを調べるパートが終了する。そうすると,SからGまでは距離4で行けることになるのだが,実際はGは安全でないマスであるため,WAである。
そこで,次のようなbfsをする。最初に@であるようなマスと残りの距離をqueueに入れてしまう。そこからは素直に安全でないマスを調べていくだけである。異なる点は最初だけだが,これでうまくいく。
うまくいくことを確認しよう。最初に@であるようなマスをqueueに入れておくと,以下のことが成り立つ。
- すべての壁以外のマスについて,がqueueに入るとき,はについて最適な値である。つまり,はから最も近い@から探索したときに得られる残りの距離である。
なぜなら,このbfsは「ある@からの距離が1のマスすべて」→「ある@からの距離が2のマスすべて」→...→「ある@からの距離がXのマスすべて」という順で探索が進むからである。また,どのマスも高々1回しか探索されないので,計算量もで済む。
提出
https://beta.atcoder.jp/contests/qupc2018/submissions/3439882
実装上の変なところ(?)は以下。
- 安全でないマスを調べる際には,queueに入れるときにマスをで管理している。なので,2000で割ったときの商とあまりでマスを復元できる。こんなことをした理由は,pair< int, pair< int,int> > と書きたくなかったからなのだが,いい方法あったら教えてください。
- とか言いつつ,2回目のbfsではマスをそのまま管理してる。何も他に情報がいらなければこう書くのが個人的には楽なためそうしている。
こういう探索の始点が複数あるbfsは割とよく見る。