グリッド上の最短経路
r 行 c 列のグリッドで表される迷路が与えられているとき、スタートのセルからゴールのセルまでの最短経路の長さを求める問題です。
迷路は以下のように表されています:
- 床はドット (
.)
- 壁はハッシュ (
#)
- スタート地点は大文字の
S
- ゴール地点は大文字の
E
壁ではない隣接セル（上下左右）であれば移動可能です。
スタートのセルからゴールのセルまでの最短経路の長さを見つけるのが目的です。
入力
最初の行には、2 つの整数
r と c (1 ≤ r, c ≤ 1000) が与えられます。続く r 行には、c 列分の文字が並んでおり、各セルは床 (
.)、壁 (#)、スタート (S)、またはゴール (E) のいずれかです。グリッド全体で S と E はそれぞれ 1 つだけ存在することが保証されています。出力
プログラムは、
S から E までの最短経路の長さを出力してください。もし S から E へ到達できる経路が存在しない場合は、Impossible を出力してください。例
Input
5 8
########
##.S....
....#.#.
#......#
...#...EOutput
7Tip
常にグラフを明示的に構築しなくても、グリッドのように暗黙的にグラフを表現して BFS を使うことができます。
Hint
グリッドをグラフとして扱い、スタートのセルから各セルへの最短距離を格納する 2 次元配列
d[][] を用いると良いでしょう。Constraints
Time limit: 15 seconds
Memory limit: 512 MB
Output limit: 1 MB