結果
問題 |
No.971 いたずらっ子
|
ユーザー |
|
提出日時 | 2022-08-15 17:43:09 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,095 bytes |
コンパイル時間 | 202 ms |
コンパイル使用メモリ | 82,792 KB |
実行使用メモリ | 806,988 KB |
最終ジャッジ日時 | 2024-10-02 06:50:43 |
合計ジャッジ時間 | 7,586 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 4 |
other | MLE * 1 -- * 20 |
ソースコード
from collections import deque h,w = map(int,input().split()) a = [input() for i in range(h)] li = [[10**9]*w for i in range(h)] d = deque() d.append([0,0,0,0]) #li[0][0] = 1 ans = 10**9 while len(d): x,y,c,s = d.popleft() if x == w-1 and y == h-1: ans = min(ans,c) #print(ans) continue #if a[y][x] == "k": # d.append([x,y,2*c]) # li[y][x] = 2*c #print(d) else: if x+1 < w: if a[y][x] != "k": if li[y][x+1] > c+1: li[y][x+1] = c+1 d.append([x+1,y,c+1,s+1]) else: if li[y][x+1] > c+s+1: li[y][x+1] = c+s+1 d.append([x+1,y,c+s+1,s+1]) if y+1 < h: if a[y][x] != "k": if li[y+1][x] > c+1: li[y+1][x] = c+1 d.append([x,y+1,c+1,s+1]) else: if li[y+1][x] > c+s+1: li[y+1][x] = c+s+1 d.append([x,y+1,c+s+1,s+1]) #print(d) #exit() print(ans)