No.3121 Prime Dance
Problem Statement
There is a grid with $H$ rows and $W$ columns.
The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by cell $(i,j)$.
Cell $(i,j)$ is a wall only when $C_{i,j}$ is #, and it is a path when $C_{i,j}$ is .,S,G.
Takahashi is initially at cell $(S_x,S_y)$.
Letting $(x,y)$ be the cell he is currently at, he may any number of times choose and perform $1$ of the following $4$ operations that moves him to a path cell.
Operation A
- Move to cell $(x+1,y)$.
Operation B
- Move to cell $(x-1,y)$.
Operation C
- Move to cell $(x,y+1)$.
Operation D
- Move to cell $(x,y-1)$.
Is there a way to move to cell $(G_x,G_y)$ by performing each operation a prime number of times?
If there is, find the minimum number of operations.
More precisely,
- Let $A$ be the number of times operation A is performed.
- Let $B$ be the number of times operation B is performed.
- Let $C$ be the number of times operation C is performed.
- Let $D$ be the number of times operation D is performed.
Determine whether there exists a sequence of operations such that $A,B,C,D$ are all prime numbers and he is at cell $(G_x,G_y)$ after those operations.
If it exists, find the minimum possible value of $A+B+C+D$.
Constraints
- $1 \leq H \le 40$
- $1 \leq W \le 40$
- $1 \le S_x,G_x \le H$
- $1 \le S_y,G_y \le W$
- $(S_x,S_y) \neq (G_x,G_y)$
- $C_{i,j}$ is one of
#,.,S,G - $C_{S_x,S_y}=$
S - $C_{G_x,G_y}=$
G - $C_{i,j} \neq$
Swhen $(i,j) \ne (S_x,S_y)$ - $C_{i,j} \neq$
Gwhen $(i,j) \ne (G_x,G_y)$
Input
The input is given from standard input in the following format.
$H$ $W$
$S_x$ $S_y$
$G_x$ $G_y$
$C_{1,1} C_{1,2} \cdots C_{1,W}$
$\vdots$
$C_{H,1} C_{H,2} \cdots C_{H,W}$
Output
If no sequence of operations satisfying the conditions exists, print -1.
If a sequence of operations satisfying the conditions exists, print the minimum number of operations.
Sample
Sample 1
Input
3 3 1 1 3 3 S.. .#. .#G
Output
16
One sequence of operations satisfying the conditions is CCDCDCDCAABABABA. Its length is $16$.
The conditions cannot be satisfied with $15$ or fewer operations.
Sample 2
Input
2 8 1 1 2 8 S....... .......G
Output
-1
The conditions cannot be satisfied no matter how the operations are performed.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。