結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 2025-07-15 18:36:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 934 ms / 3,000 ms |
コード長 | 2,084 bytes |
コンパイル時間 | 334 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 122,292 KB |
最終ジャッジ日時 | 2025-07-15 18:36:46 |
合計ジャッジ時間 | 12,528 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
from collections import Counter, deque, defaultdict from heapq import heapify, heappop, heappush, nlargest, nsmallest from bisect import bisect_left, bisect, bisect_right from string import ascii_lowercase, ascii_uppercase, digits from copy import deepcopy from time import perf_counter import sys from typing import Any, List, Callable def debug(*args, sep=" ", end="\n") -> None: print(*args, sep=sep, end=end, file=sys.stderr) def yn(b): print('Yes' if b else 'No') return b def gcd(a, b): a = abs(a); b = abs(b) if a < b: a, b = b, a while b > 0: a, b = b, a % b return a def lcm(a, b): return a * b // gcd(a, b) def main(): global inf, MOD input = sys.stdin.read().split() ptr = 0 inf = float("inf") MOD = 998244353 H, W, M = map(int, input[ptr:ptr + 3]); ptr += 3 G = input[ptr:ptr + H]; ptr += H N = H * W def encode(r, i, j): return r * N + i * W + j def decode(x): r = x // N x %= N i = x // W j = x % W return r, i, j for i in range(H): for j in range(W): if G[i][j] == "S": s, t = i, j break x = encode(0, s, t) q = deque([(0, x)]) seen = [False] * N * (M + 1) seen[x] = True while q: d, x = q.popleft() r, i, j = decode(x) if G[i][j] == "G": print(d) break for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]: ni, nj = i + di, j + dj if 0 <= ni < H and 0 <= nj < W and G[ni][nj] != "#": if G[ni][nj] in digits: nr = int(G[ni][nj]) else: nr = r xx = encode(nr, ni, nj) if seen[xx]: continue if G[ni][nj] in ascii_lowercase and nr != ascii_lowercase.index(G[ni][nj]) + 1: continue q.append((d + 1, xx)) seen[xx] = True else: print(-1) if __name__ == "__main__": main()