7K12 blog

猫でも分かるアルゴリズム解説

ABC151 D - Maze Master

f:id:tkr987:20200718025205p:plain

https://atcoder.jp/contests/abc151/submissions/13015367

https://atcoder.jp/contests/abc151/submissions/15292083

  • スタート地点が#の時どこにも移動できないので何もせず結果を返すことに注意

f:id:tkr987:20200718025350p:plain

制約が縦横20しかないことから O(V^3) O(H^3 W^3)が許される。つまり、スタート地点とゴール地点を全て試して最短経路の最大値を求めても間に合う。実装方法は2つ考えられる。1つはグリッド情報からグラフに変換してワーシャルフロイド法を使う実装。もう1つはグリッド情報のまま4方向BFSを実行する実装。