結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 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 |
ソースコード
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)