問題一覧 > 通常問題

No.3199 Key-Door Grid

レベル : / AI推定難易度 : 1100 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 114
作問者 : YY-otter / テスター : nauclhlt
お気に入りにしたユーザー ProblemId : 12432 / 自分の提出
問題文最終更新日: 2026-10-16 19:43:57
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
yukicoder contest 473 第1回 生成AI作問コンテスト (順位表) の他の問題:

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 point
  • G: a passage that is the goal point
  • 1~9: a passage where a "key" of the corresponding type is placed
  • a~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.

  1. From your current cell, you can move $1$ cell at a time to a cell adjacent vertically or horizontally.
  2. You cannot move onto a wall cell.
  3. You start without any key, and you can hold only $1$ key at a time.
  4. 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.
  5. To pass through a door cell, you must hold the key of the type corresponding to that door.
  6. 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 S and G exactly $1$ time each
  • As for the key characters in $S$, each of 1 through $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 key 1 [$2$ moves]
  • Pass through door a at $(3,3)$ using key 1 [$2$ moves]
  • At $(3,2)$, discard key 1 and pick up key 2 [$1$ move]
  • From there, head to $(5,5)$, which is the goal G [$5$ moves]
The total number of moves is $10$.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。