Description

In the year $1944$, special forces soldier Mike received an order from the Ministry of Defense to rush to a deserted island in the Pacific to rescue Private Ryan, who had been captured by the enemy. Ryan is imprisoned in a maze. The maze is complex, but fortunately Mike has obtained a map of it. The maze is rectangular, divided into $N$ rows from north to south and $M$ columns from west to east, so the entire maze consists of $N \times M$ cells. The position of each cell is represented by an ordered pair (row, column). Two adjacent cells in the north-south or east-west direction may be connected, or there may be a locked door between them, or an impassable wall. Some cells contain keys. All doors are divided into $P$ classes; keys that open doors of the same class are identical, and keys for different classes are different.

Private Ryan is held in the southeast corner of the maze, i.e., in cell $(N, M)$, and is unconscious. The maze has only one entrance at the northwest corner. That is, Mike can directly enter cell $(1, 1)$. The time for Mike to move from one cell to an adjacent cell is $1$. The time to pick up a key in the current cell and to unlock a door is negligible.

Design an algorithm to help Mike reach the cell where Ryan is as quickly as possible and rescue him.

Input Format

• The first line contains $3$ integers, representing the values of $N$, $M$, and $P$.
• The second line contains $1$ integer $K$, the total number of doors and walls in the maze.
• The $I+2$-th line ($1 \leq I \leq K$) contains $5$ integers, in order $X_{i1}, Y_{i1}, X_{i2}, Y_{i2}, G_i$:
  • When $G_i \geq 1$, there is a class-$G_i$ door between cells $(X_{i1}, Y_{i1})$ and $(X_{i2}, Y_{i2})$.
  • When $G_i = 0$, there is an impassable wall between cells $(X_{i1}, Y_{i1})$ and $(X_{i2}, Y_{i2})$ (where $|X_{i1} - X_{i2}| + |Y_{i1} - Y_{i2}| = 1$, $0 \leq G_i \leq P$).
• The $K+3$-th line contains an integer $S$, the total number of keys in the maze.
• The $K+3+J$-th line ($1 \leq J \leq S$) contains $3$ integers, in order $X_{j}, Y_{j}, Q_j$: the $J$-th key is placed in cell $(X_{j}, Y_{j})$, and it opens doors of class $Q_j$ (where $1 \leq Q_j \leq P$).

Adjacent integers on the same line in the input are separated by a single space.

Output Format

Output the minimum time for Mike to rescue Private Ryan. If the problem has no solution, output $-1$.

4 4 9
9
1 2 1 3 2
1 2 2 2 0
2 1 2 2 0
2 1 3 1 0
2 3 3 3 0
2 4 3 4 1
3 2 3 3 0
3 3 4 3 0
4 3 4 4 0
2
2 1 2
4 2 1

14

Hint

$|X_{i1} - X_{i2}| + |Y_{i1} - Y_{i2}| = 1$, $0 \leq G_i \leq P$.

$1 \leq Q_j \leq P$.

Constraints: $N, M, P \leq 10$, $K < 150$, $S \leq 14$.

Translated by ChatGPT 5