No.3199 Key-Door Grid
Problem Statement
There is a maze consisting of a grid with $H$ rows and $W$ columns.
You will explore this maze, aiming to get from the start point S to the goal point G in the fewest possible moves.
Each cell of the maze is represented by one of the following characters.
.: a passage#: a wall (impassable)S: a passage that is the start pointG: a passage that is the goal point1~9: a passage where a "key" of the corresponding type is placeda~i: a passage with a "door" of the corresponding type
There are $M$ types of keys in the maze. Key $k\ (1\leq k\leq M)$ can open doors corresponding to the $k$-th lowercase letter of the alphabet (a for 1, b for 2, ...).
You move according to the following rules.
- From your current cell, you can move $1$ cell at a time to a cell adjacent vertically or horizontally.
- You cannot move onto a wall cell.
- You start without any key, and you can hold only $1$ key at a time.
- When you move onto a cell where a key is placed, you automatically pick up that key. At that time, the key you had been holding returns to its original location, and you switch to the new key.
- To pass through a door cell, you must hold the key of the type corresponding to that door.
- Passing through a door does not consume the key, and even after a door has been opened, it returns to the locked state once you switch keys.
Find the minimum number of moves from the start point S to the goal point G. If you cannot reach the goal, print -1.
Input
$H\ W\ M$ $S_1$ $\vdots$ $S_H$
- $2\leq H,W\leq 500$
- $0\leq M\leq 9$
- $S_i$ is a string of length $W$ consisting of the characters shown in the problem statement
- $S$ contains
SandGexactly $1$ time each - As for the key characters in $S$, each of
1through $M$ appears at least $1$ time, and no other digits are contained - Each door character in $S$ is one of the $1$-st through $M$-th lowercase letters of the alphabet (when $M=0$, no doors are contained)
Output
Print the minimum number of moves to the goal. If the goal is unreachable, print -1.
Print a newline at the end.
Sample
Sample 1
Input
5 5 2 S.1.. ##.## .2a.. #.### ....G
Output
10
This maze has $2$ types of keys (1, 2) and $1$ type of door (a).
One example of a shortest path is as follows:
- Move from $(1,1)$, which is
S, to $(1,3)$ and pick up key1[$2$ moves] - Pass through door
aat $(3,3)$ using key1[$2$ moves] - At $(3,2)$, discard key
1and pick up key2[$1$ move] - From there, head to $(5,5)$, which is the goal
G[$5$ moves]
Sample 2
Input
2 3 2 S#G 12a
Output
-1
You move from $(1,1)$, which is S, to $(2,1)$ and pick up key 1, but moving to $(2,2)$ makes you pick up key 2 and discard key 1.
You cannot pass through door a at $(2,3)$ and cannot reach the goal G, so print -1.
Sample 3
Input
9 9 3 bbbbbbbbb bS1cc3bcb b3acbb2cb b2a1bcc3b aaacbb1cb accc3cbcb a2aaacbbb acccacccc aaaaaaacG
Output
24
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
nauclhlt