結果
問題 |
No.2913 二次元距離空間
|
ユーザー |
![]() |
提出日時 | 2024-10-04 22:22:16 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,316 bytes |
コンパイル時間 | 154 ms |
コンパイル使用メモリ | 82,464 KB |
実行使用メモリ | 79,104 KB |
最終ジャッジ日時 | 2024-10-04 22:22:19 |
合計ジャッジ時間 | 2,779 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 WA * 7 |
ソースコード
from collections import deque H, W = map(int, input().split()) S = [input() for _ in range(H)] visited = [[-1]*W for _ in range(H)] visited[0][0] = (0, 0) que = deque() que.append((0, 0)) direction = [(-1,0),(0,1),(1,0),(0,-1)] while que: h, w = que.popleft() wcnt, hcnt = visited[h][w] for dh, dw in direction: nh, nw = h+dh, w+dw if 0<=nh<H and 0<=nw<W and S[nh][nw] == ".": if dh != 0: if visited[nh][nw] == -1: visited[nh][nw] = (wcnt, hcnt+1) que.appendleft((nh, nw)) else: nwcnt, nhcnt = visited[h][w] if wcnt < nwcnt or wcnt == nwcnt and hcnt+1 < nhcnt: visited[nh][nw] = (wcnt, hcnt+1) que.appendleft((nh, nw)) else: if visited[nh][nw] == -1: visited[nh][nw] = (wcnt+1, hcnt) que.append((nh, nw)) else: nwcnt, nhcnt = visited[h][w] if wcnt+1 < nwcnt or wcnt+1 == nwcnt and hcnt < nhcnt: visited[nh][nw] = (wcnt+1, hcnt) que.append((nh, nw)) if visited[-1][-1] != -1: print("Yes") print(*visited[-1][-1]) else: print("No")