問題一覧 > 通常問題

No.3121 Prime Dance

レベル : / AI推定難易度 : 2425 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 21
作問者 : Nzt3 / テスター : ponjuice kenken714 Naru820
お気に入りにしたユーザー ProblemId : 12105 / 自分の提出
問題文最終更新日: 2025-04-18 00:29:22
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
CPCTF 2025 : PPC (順位表) の他の問題:

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$ S when $(i,j) \ne (S_x,S_y)$
  • $C_{i,j} \neq$ G when $(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もしくは右上の雲マークをクリックしてアカウントを作成してください。