AT_icpc2013summer_warmingUp_e Magic Doors
Description
[problemUrl]: https://atcoder.jp/contests/jag2013summer-warmingup/tasks/icpc2013summer_warmingUp_e
Wizard KM often forgets to close doors.
So he invented the magic door which opens with a magic spell and automatically closes after a while.
He put the doors in many places in his house, so it became very difficult to move around.
He wants to know the shortest time to move between two places in his house, so he cast a magic spell and summoned you, the excellent programmer.
KM's house consists of a matrix of square cells. A cell is one of the followings.
```
. empty
# wall
^ start
$ goal
a-h\ magic\ circle
A-H\ magic\ door
He\ can\ move\ one\ cell\ to\ its\ 4 $-neighborhood in a second.
He can move into empty cells, start, goal, magic circles, and opened magic doors.
The house is surrounded by the walls, so he can't go out.
On a magic circle, he can cast a magic spell by consuming arbitrary amount of MP (Magic power). This takes a second. When he uses $ x $ MP, the corresponding magic doors opens during $ x $ seconds.
He can move into a door which closes at that time.
There may be more than one same magic circles or same magic doors. In this case, all the corresponding magic doors opens when he cast a magic spell on any magic circles.
At the beginning, his MP is $ 0 $. He can meditate at arbitrary timing and restore MP. Meditation takes a second per $ 1 $ MP. There is no upper bound of MP.
Find the shortest time to move from the start to the goal.
The first line of the input file contains two integers $ H $ and $ W $ ($ 1\ \leq\ H,\ W\ \leq\ 30 $).
Subsequent $ H $ lines of $ W $ characters $ \{c_{ij}\} $ are the map of KM's house.
Each character $ c_{ij} $ is one of the letters ``` . ```, ``` # ```, ``` ^ ```, ``` $ ,\ a-h,\ A-H. There\ is\ only\ one\ start\ and\ one\ goal\ in\ the\ map. Output\ the\ shortest\ time\ by\ the\ second. If\ it\ is\ impossible\ to\ reach\ the\ goal,\ output\ -1\ instead. 1\ 3 ^. $ ``` ``` ``` 2 ``` ``` 1 4 ^aA$ 5 1\ 4 ^aB $ ``` ``` -1 ``` ``` 3 3 ^AB a#A b#$ ``` ``` 19 ```
He can move into empty cells, start, goal, magic circles, and opened magic doors.
The house is surrounded by the walls, so he can't go out.
On a magic circle, he can cast a magic spell by consuming arbitrary amount of MP (Magic power). This takes a second. When he uses $ x $ MP, the corresponding magic doors opens during $ x $ seconds.
He can move into a door which closes at that time.
There may be more than one same magic circles or same magic doors. In this case, all the corresponding magic doors opens when he cast a magic spell on any magic circles.
At the beginning, his MP is $ 0 $. He can meditate at arbitrary timing and restore MP. Meditation takes a second per $ 1 $ MP. There is no upper bound of MP.
Find the shortest time to move from the start to the goal.
The first line of the input file contains two integers $ H $ and $ W $ ($ 1\ \leq\ H,\ W\ \leq\ 30 $).
Subsequent $ H $ lines of $ W $ characters $ \{c_{ij}\} $ are the map of KM's house.
Each character $ c_{ij} $ is one of the letters ``` . ```, ``` # ```, ``` ^ ```, ``` $ ,\ a-h,\ A-H. There\ is\ only\ one\ start\ and\ one\ goal\ in\ the\ map. Output\ the\ shortest\ time\ by\ the\ second. If\ it\ is\ impossible\ to\ reach\ the\ goal,\ output\ -1\ instead. 1\ 3 ^. $ ``` ``` ``` 2 ``` ``` 1 4 ^aA$ 5 1\ 4 ^aB $ ``` ``` -1 ``` ``` 3 3 ^AB a#A b#$ ``` ``` 19 ```
Input Format
N/A
Output Format
N/A