結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー Yakumo221
提出日時 2025-07-12 01:49:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 825 ms / 3,000 ms
コード長 1,812 bytes
コンパイル時間 433 ms
コンパイル使用メモリ 81,852 KB
実行使用メモリ 103,048 KB
最終ジャッジ日時 2025-07-12 01:49:42
合計ジャッジ時間 12,645 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

def encode(li):
    val = 0
    for i in range(m):
        val *= 3
        val += li[i]
    
    return val

def decode(val):
    li = [0 for i in range(m)]
    for i in range(m):
        val, res = divmod(val, 3)
        li[m-1-i] = val
    
    return li

h,w,m = map(int, input().split())
sli = [input()+"#" for i in range(h)] + ["#" * (w+1)]

dig = [[[ 1 << 60 for i in range(w)] for i in range(h)] for i in range(10)]

# 4方向
dlist = [(-1,0), (1,0), (0,-1), (0,1)]

for i in range(h):
    for j in range(w):
        if sli[i][j] == "S":
            si, sj = i,j
        if sli[i][j] == "G":
            gi,gj = i,j

dig[0][si][sj] = 0

que = [(0, si, sj)]

while que:
    nq = []
    while que:
        state, i,j = que.pop()
        for di,dj in dlist:
            ni,nj = i+di, j+dj

            if sli[ni][nj] == "#":
                continue

            if sli[ni][nj] == ".":
                pass
            elif sli[ni][nj] == "S":
                pass
            elif sli[ni][nj] == "G":
                pass
            elif "a" <= sli[ni][nj] <= "i":
                door = ord(sli[ni][nj]) - ord("a") + 1
                if state != door :
                    continue
            elif "1" <= sli[ni][nj] <= "9":
                ns = int(sli[ni][nj])
                if dig[ns][ni][nj] <= (dig[state][i][j] + 1):
                    continue
                dig[ns][ni][nj] = (dig[state][i][j] + 1)
                nq.append((ns,ni,nj))
                continue

            if dig[state][ni][nj] <= (dig[state][i][j] + 1):
                continue
            dig[state][ni][nj] = (dig[state][i][j] + 1)
            nq.append((state, ni, nj))
    
    que = nq

ans = 1 << 60

for i in range(10):
    ans = min(ans, dig[i][gi][gj])

if ans == (1 << 60):
    print(-1)
else:
    print(ans)
0