結果
問題 |
No.971 いたずらっ子
|
ユーザー |
|
提出日時 | 2022-04-19 23:34:23 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 593 bytes |
コンパイル時間 | 294 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 178,816 KB |
最終ジャッジ日時 | 2025-01-02 18:59:33 |
合計ジャッジ時間 | 30,138 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 12 WA * 2 TLE * 7 |
ソースコード
from heapq import heappop,heappush H,W = map(int,input().split()) A = [input() for i in range(H)] inf = 10**10 dis = [[inf]*W for i in range(H)] dis[0][0] = 0 h = [[0,0,0,0]] dx = [1,0,-1,0] dy = [0,1,0,-1] while h: d,d2,x,y = heappop(h) if dis[x][y] != d: continue for i in range(4): nx = x+dx[i] ny = y+dy[i] if 0 <= nx < H and 0 <= ny < W: p = int(A[nx][ny] == "k") if dis[nx][ny] > d + 1 + p*(d2+1): dis[nx][ny] = d + 1 + p*(d2+1) heappush(h,[dis[nx][ny],d2+1,nx,ny]) print(dis[-1][-1])