C： AA グラフ (AA Graph)

問題

グラフが AA（ASCII art）として与えられる。頂点 s から頂点 t への最短経路を出力せよ。

与えられるグラフは以下の制約を満たす。

頂点は大文字アルファベットとその 8 近傍の o で表される。

ooo
oAo
ooo

横向きの辺は - で表され、縦向きの辺は | で表される。 辺の長さは全て 1 である。- や | がいくつ連続しているかは、辺の長さとは関係ない。

辺と辺は交差しない。また、頂点と頂点が重なったり、接することもない。

各頂点から出る辺は上下左右それぞれについて高々一本である。それぞれの辺は下の図のように、頂点を表すアルファベットの上下左右にある o に接続する。

..|..
.ooo.
-oAo-
.ooo.
..|..

したがって、以下のような入力はない。

..........
.ooo..ooo.
.oAo..oBo.
.ooo--ooo.
..........

（辺の位置が条件を満たしていない）

oooooo
oAooBo
oooooo

（頂点と頂点が接してしまっている）

入力形式

H W s t
a_1
$\vdots$
a_H

• 1 行目には、AAの縦幅を表す整数 H と横幅を表す整数 W 、始点の頂点を表す文字 s 、終点の頂点を表す文字 t が空白区切りで与えられる。
• 1 + i 行目 (1 \leq i \leq H) には、AAの i 行目を表す文字列が与えられる。

制約

• 3 \leq H, W \leq 50
• s と t はそれぞれ A から Z のいずれかであり s \neq t を満たす。
• a_i (1 \leq i \leq H) は A から Z および o、-、|、. のみからなる。
• 各文字 A から Z はAA中に高々1回しか出現しない。
• s, t を表す頂点は必ずグラフに存在する。
• 入力は全て連結なグラフである。
• 頂点と頂点、辺と辺が重なることはない。
• 辺の長さは見かけの長さと関係なく、全て 1 である。
• 各頂点に接続する辺は上下左右にそれぞれ高々 1 本である。
• 辺の端は頂点を表す大文字アルファベットに 4 近傍で隣接する o のいずれかに接続する。

出力形式

AAで与えられるグラフ上での s から t への最短経路長を 1 行に出力せよ。

入力例1

14 16 A L 
ooo.....ooo.....
oAo-----oHo.....
ooo.....ooo..ooo
.|.......|...oLo
ooo..ooo.|...ooo
oKo--oYo.|....|.
ooo..ooo.|....|.
.|....|.ooo...|.
.|....|.oGo...|.
.|....|.ooo...|.
.|....|.......|.
ooo..ooo.....ooo
oFo--oXo-----oEo
ooo..ooo.....ooo

出力例1

5

入力例2

21 17 F L
.................
.....ooo.....ooo.
.....oAo-----oBo.
.....ooo.....ooo.
......|.......|..
.ooo..|..ooo..|..
.oCo..|..oDo.ooo.
.ooo.ooo.ooo.oEo.
..|..oFo..|..ooo.
..|..ooo..|...|..
..|...|...|...|..
..|...|...|...|..
..|...|...|...|..
.ooo.ooo.ooo..|..
.oGo-oHo-oIo..|..
.ooo.ooo.ooo..|..
..|...........|..
.ooo...ooo...ooo.
.oJo---oKo---oLo.
.ooo...ooo...ooo.
.................

出力例2

4

Note

Link

 

---