QUPC2018-C:Ito Campus

慣れているとなんてことない問題だが,ちゃんと書いてみる。

解説

@から距離X以内のマスは安全でないなので,そのようなマスを調べて安全でないマークをつけてから,安全なマスだけでSからGへの最短距離を調べればよい。安全でないマスを調べるのも,SからGへの最短距離を調べるのも,幅優先探索(以下bfs)すればよいのだが,前者については注意が必要という問題である。
例えば,「@を見つけたら,そこからbfsで距離X以内のマスに安全でないマークをつける」ということをすると,毎回のbfsにO(X)かかり,@がいっぱいあると計算量がO(XHW)となり,TLEする。
では,「安全でないマークをつけたマスは壁'#'にしてしまう」というアイデアはどうか。これならば,同じマスを2度以上探索しないのでTLEは回避できる。しかし,これではWAを踏んでしまう。例えば,X=3として,以下のような状況を考えてみよう。外側の壁は省略してある。
f:id:sigma1113:20181020185553p:plain
ここで,(1,1)にある@から探索をすると,以下のようになる。
f:id:sigma1113:20181020185655p:plain
これで,(3,1)からあるマスを探索しようとしても,イノシシは壁を通れないので,ここで安全でないマスを調べるパートが終了する。そうすると,SからGまでは距離4で行けることになるのだが,実際はGは安全でないマスであるため,WAである。

そこで,次のようなbfsをする。最初に@であるようなマスと残りの距離(x,y,d)をqueueに入れてしまう。そこからは素直に安全でないマスを調べていくだけである。異なる点は最初だけだが,これでうまくいく。
うまくいくことを確認しよう。最初に@であるようなマスをqueueに入れておくと,以下のことが成り立つ。

  • すべての壁以外のマスに(x,y)ついて,(x,y,d)がqueueに入るとき,d(x,y)について最適な値である。つまり,d(x,y)から最も近い@から探索したときに得られる残りの距離である。

なぜなら,このbfsは「ある@からの距離が1のマスすべて」→「ある@からの距離が2のマスすべて」→...→「ある@からの距離がXのマスすべて」という順で探索が進むからである。また,どのマスも高々1回しか探索されないので,計算量もO(HW)で済む。

提出

https://beta.atcoder.jp/contests/qupc2018/submissions/3439882
実装上の変なところ(?)は以下。

  • 安全でないマスを調べる際には,queueに入れるときにマス(x,y)2000\times x+yで管理している。y\leq 1000なので,2000で割ったときの商とあまりでマス(x,y)を復元できる。こんなことをした理由は,pair< int, pair< int,int> > と書きたくなかったからなのだが,いい方法あったら教えてください。
  • とか言いつつ,2回目のbfsではマス(x,y)をそのまま管理してる。何も他に情報がいらなければこう書くのが個人的には楽なためそうしている。


こういう探索の始点が複数あるbfsは割とよく見る。