/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
H 行 W 列のマス目からなる迷路があります。 上から i 行目、左から j 列目のマスを (i,j) と表記します。 マス (i,j) がどのようなマスであるかは文字 S_{i,j} として与えられ、各文字の意味は以下の通りです。
.: 空きマス#: 障害物マス- 英小文字（
a-z）: ワープマス
迷路内では、以下の二種類の行動を好きな順序で何回でも行うことができます。
- 歩行：現在いるマスから上下左右の四方向のいずれかに 1 マス分進んだマスへ移動する。ただし、障害物マスへ移動することや、マス目の外に移動することはできない。
- ワープ：ワープマスにいるとき、そのワープマスと同じ文字が書かれたワープマスのうちいずれか好きなマスへと移動する。
マス (1,1) からマス (H,W) へ移動することが可能かどうか判定し、可能ならばそれに必要な最小の合計行動回数を求めてください。
制約
- 1\leq H,W \leq 1000
- H\times W \geq 2
- H,W は整数
- S_{i,j} は
.,#, または英小文字のいずれか - S_{1,1}\neq
# - S_{H,W}\neq
#
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{1,1}S_{1,2}\dots S_{1,W}
\vdots
S_{H,1}S_{H,2}\dots S_{H,W}
出力
マス (1,1) からマス (H,W) へ移動することが可能ならばそれに必要な最小の合計行動回数を、不可能ならば -1 を出力せよ。
入力例 1
3 4 ..a. #### ba#b
出力例 1
5
以下のように行動することで、マス (1,1) からマス (3,4) へ移動することができます。
- マス (1,1) からマス (1,2) へ歩行によって移動する。
- マス (1,2) からマス (1,3) へ歩行によって移動する。
- マス (1,3) からマス (3,2) へワープによって移動する。
- マス (3,2) からマス (3,1) へ歩行によって移動する。
- マス (3,1) からマス (3,4) へワープによって移動する。
このときの合計行動回数は 5 回であり、これが最小です。
入力例 2
3 4 ..a. #### b.#b
出力例 2
-1
マス (1,1) からマス (3,4) へ移動することは不可能です。
入力例 3
4 4 xxxx xxxx xxxx xxxx
出力例 3
1
入力例 4
7 11 u..#y..#... k..#.z.#.k. iju#...#x.. ########### ..x#.t.#..n abc#y..#... ..z#..t#.y.
出力例 4
12
Score : 400 points
Problem Statement
There is a maze consisting of a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. The type of cell (i,j) is given as a character S_{i,j}, where each character has the following meaning:
.: Empty cell#: Obstacle cell- Lowercase English letter (
a-z): Warp cell
In the maze, you can perform the following two types of actions any number of times in any order:
- Walk: Move from the current cell to a cell that is one cell away in one of the four directions (up, down, left, right). However, you cannot move to an obstacle cell or outside the grid.
- Warp: When you are at a warp cell, move to any warp cell with the same character written on it.
Determine whether it is possible to move from cell (1,1) to cell (H,W), and if possible, find the minimum total number of actions required.
Constraints
- 1\leq H,W \leq 1000
- H\times W \geq 2
- H and W are integers.
- S_{i,j} is
.,#, or a lowercase English letter. - S_{1,1}\neq
# - S_{H,W}\neq
#
Input
The input is given from Standard Input in the following format:
H W
S_{1,1}S_{1,2}\dots S_{1,W}
\vdots
S_{H,1}S_{H,2}\dots S_{H,W}
Output
If it is possible to move from cell (1,1) to cell (H,W), print the minimum total number of actions required; otherwise, print -1.
Sample Input 1
3 4 ..a. #### ba#b
Sample Output 1
5
You can move from cell (1,1) to cell (3,4) by performing actions as follows:
- Move from cell (1,1) to cell (1,2) by walking.
- Move from cell (1,2) to cell (1,3) by walking.
- Move from cell (1,3) to cell (3,2) by warping.
- Move from cell (3,2) to cell (3,1) by walking.
- Move from cell (3,1) to cell (3,4) by warping.
The total number of actions is 5, which is the minimum.
Sample Input 2
3 4 ..a. #### b.#b
Sample Output 2
-1
It is impossible to move from cell (1,1) to cell (3,4).
Sample Input 3
4 4 xxxx xxxx xxxx xxxx
Sample Output 3
1
Sample Input 4
7 11 u..#y..#... k..#.z.#.k. iju#...#x.. ########### ..x#.t.#..n abc#y..#... ..z#..t#.y.
Sample Output 4
12