問題一覧 > 通常問題

No.3199 Key-Door Grid

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 111
作問者 : YY-otter / テスター : Nauclhlt🪷
ProblemId : 12432 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-07-11 11:50:53

問題文

$H$ 行 $W$ 列のグリッドで構成された迷宮があります。
あなたはその迷宮を探検し、スタート地点Sからゴール地点Gまで、最も少ない移動回数でたどり着くことを目指します。

迷宮の各マスは、以下のいずれかの文字で表されます。

  • .: 通路
  • #: 壁（通れない）
  • S: スタート地点である通路
  • G: ゴール地点である通路
  • 1~9: 対応する種類の「鍵」が置かれている通路
  • a~i: 対応する種類の「扉」がある通路

迷宮には $M$ 種類の鍵が存在します。鍵 $k\ (1\leq k\leq M)$ は、アルファベットの $k$ 番目の小文字に対応する扉（1ならa、2ならb、...）を開けることができます。

あなたは、以下のルールに従って移動します。

  1. 現在いるマスから、上下左右に隣接するマスへ $1$ マスずつ移動できます。
  2. 壁のマスへは移動できません。
  3. あなたは最初鍵を持っていない状態からスタートし、一度に $1$ つだけ鍵を持つことができます。
  4. 鍵が置かれているマスに移動すると、あなたは自動的にその鍵を拾います。その際、それまで持っていた鍵はもとあった場所に戻り、新しい鍵に持ち替えます。
  5. 扉のマスを通過するためには、その扉に対応した種類の鍵を持っている必要があります。
  6. 扉は通過しても鍵を消費することはなく、また、一度開けても鍵を持ち替えれば再び施錠された状態に戻ります。

スタート地点Sからゴール地点Gまでの最小移動回数を求めてください。もし、ゴールにたどり着けない場合は-1を出力してください。

入力

$H\ W\ M$
$S_1$
$\vdots$
$S_H$

  • $2\leq H,W\leq 500$
  • $0\leq M\leq 9$
  • $S_i$ は、問題文中で示された文字で構成された長さ $W$ の文字列
  • $S$ にはSとGがちょうど $1$ つずつ含まれる

出力

ゴールまでの最小移動回数を出力してください。到達不能な場合は-1を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
5 5 2
S.1..
##.##
.2a..
#.###
....G
出力
10

この迷宮には $2$ 種類の鍵(1, 2)と、$1$ 種類の扉(a)が存在します。
最短経路の一例は、

  • Sである $(1,1)$ から $(1,3)$ へ移動して鍵1を拾い[移動 $2$ 回]
  • $(3,3)$ にある扉aを鍵1で通過し[移動 $2$ 回]
  • $(3,2)$ で鍵1を捨てて鍵2を拾い[移動 $1$ 回]
  • そこからゴールのGである $(5,5)$ へ向かう[移動 $5$ 回]
というもので、合計移動回数は $10$ 回です。

サンプル2
入力
2 3 2
S#G
12a
出力
-1

Sである $(1,1)$ から $(2,1)$ へ移動して鍵1を拾いますが、$(2,2)$ へ移動すると鍵2を拾い鍵1を捨てます。
$(2,3)$ の扉aを通過できず、ゴールのGにたどり着くことができないため-1を出力します。

サンプル3
入力
9 9 3
bbbbbbbbb
bS1cc3bcb
b3acbb2cb
b2a1bcc3b
aaacbb1cb
accc3cbcb
a2aaacbbb
acccacccc
aaaaaaacG
出力
24

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。