結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー 学ぶマン
提出日時 2025-07-11 22:42:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 964 ms / 3,000 ms
コード長 3,072 bytes
コンパイル時間 367 ms
コンパイル使用メモリ 81,804 KB
実行使用メモリ 153,272 KB
最終ジャッジ日時 2025-07-11 22:43:02
合計ジャッジ時間 13,560 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys, math
sys.setrecursionlimit(10**8)
sys.set_int_max_str_digits(0)
INF = 10**18
MOD = 998244353
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import product, combinations, permutations, groupby, accumulate
from heapq import heapify, heappop, heappush
def I():   return sys.stdin.readline().rstrip()
def II():  return int(sys.stdin.readline().rstrip())
def IS():  return sys.stdin.readline().rstrip().split()
def MII(): return map(int, sys.stdin.readline().rstrip().split())
def LI():  return list(sys.stdin.readline().rstrip())
def TII(): return tuple(map(int, sys.stdin.readline().rstrip().split()))
def LII(): return list(map(int, sys.stdin.readline().rstrip().split()))
def LSI(): return list(map(str, sys.stdin.readline().rstrip().split()))
def GMI(): return list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))
def kiriage(a, b): return (a+b-1)//b
def chmax(DP,i,v):
    if DP[i] < v: DP[i] = v
def chmin(DP,i,v):
    if DP[i] > v: DP[i] = v

nums = set(list('123456789'))
alps = set(list('abcdefghi'))

d = {}
d['a'] = 1
d['b'] = 2
d['c'] = 3
d['d'] = 4
d['e'] = 5
d['f'] = 6
d['g'] = 7
d['h'] = 8
d['i'] = 9

H, W, M = MII()
S = [LI() for _ in range(H)]

def check(i:int, j:int):
    return 0 <= i < H and 0 <= j < W

si, sj = -1, -1
ti, tj = -1, -1
for i in range(H):
    for j in range(W):
        if S[i][j] == 'S':
            si, sj = i, j
            S[i][j] = '.'
        if S[i][j] == 'G':
            ti, tj = i, j

dist = [[[-1] * (10) for _ in range(W)] for _ in range(H)]
dist[si][sj][0] = 0
# 答えは
# dist[ti][tj][*] の最小値

que = deque()
que.append((0, si, sj, 0))
while que:
    curr_dist, i, j, k = que.popleft()

    for ii, jj in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        ni, nj = i+ii, j+jj
        if not check(ni, nj):
            continue

        if S[ni][nj] == '.':
            # k 不変
            # 未訪問なら探索
            if dist[ni][nj][k] == -1:
                dist[ni][nj][k] = curr_dist + 1
                que.append((curr_dist + 1, ni, nj, k))
        
        elif S[ni][nj] in nums:
            nexk = int(S[ni][nj])
            # k 不変
            if nexk == k:
                # 未訪問なら探索
                if dist[ni][nj][k] == -1:
                    dist[ni][nj][k] = curr_dist + 1
                    que.append((curr_dist + 1, ni, nj, k))
            # k 変更
            else:
                # 未訪問
                if dist[ni][nj][nexk] == -1:
                    dist[ni][nj][nexk] = curr_dist + 1
                    que.append((curr_dist + 1, ni, nj, nexk))

        elif S[ni][nj] in alps:
            # 今手持ちの鍵と一致してるなら探索する
            # d[英字] == 数字（鍵）
            if d[S[ni][nj]] == k:
                if dist[ni][nj][k] == -1:
                    dist[ni][nj][k] = curr_dist + 1
                    que.append((curr_dist + 1, ni, nj, k))
        
        elif S[ni][nj] == 'G':
            exit(print(curr_dist + 1))

print(-1)
0