結果
問題 |
No.971 いたずらっ子
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:31:56 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,171 bytes |
コンパイル時間 | 301 ms |
コンパイル使用メモリ | 81,664 KB |
実行使用メモリ | 667,328 KB |
最終ジャッジ日時 | 2025-06-12 21:33:03 |
合計ジャッジ時間 | 11,230 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 4 |
other | WA * 1 MLE * 5 -- * 15 |
ソースコード
import sys from collections import deque def main(): H, W = map(int, sys.stdin.readline().split()) grid = [] for _ in range(H): line = sys.stdin.readline().strip() grid.append(list(line)) INF = float('inf') dist = [[[INF] * 2 for _ in range(W + 1)] for __ in range(H + 1)] dist[1][1][0] = 0 q = deque() q.append((1, 1, 0)) dirs = [(0, 1), (1, 0)] # east, south while q: r, c, s = q.popleft() current_dist = dist[r][c][s] for dr, dc in dirs: nr = r + dr nc = c + dc if nr > H or nc > W: continue new_dist = current_dist + 1 if grid[nr-1][nc-1] == 'k': new_s = 1 if new_dist < dist[1][1][new_s]: dist[1][1][new_s] = new_dist q.append((1, 1, new_s)) else: if new_dist < dist[nr][nc][s]: dist[nr][nc][s] = new_dist q.append((nr, nc, s)) x = min(dist[H][W][0], dist[H][W][1]) print(x) if __name__ == "__main__": main()