結果
問題 |
No.2913 二次元距離空間
|
ユーザー |
![]() |
提出日時 | 2024-10-04 22:56:08 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 941 bytes |
コンパイル時間 | 267 ms |
コンパイル使用メモリ | 82,352 KB |
実行使用メモリ | 82,356 KB |
最終ジャッジ日時 | 2024-10-04 22:56:11 |
合計ジャッジ時間 | 3,388 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 WA * 1 |
ソースコード
import sys input = sys.stdin.readline from collections import deque H,W=map(int,input().split()) MAP=[input().strip() for i in range(H)] DX=[[1<<60]*W for i in range(H)] DY=[[1<<60]*W for i in range(H)] DX[0][0]=0 DY[0][0]=0 Q=deque([(0,0)]) while Q: x,y=Q.popleft() for z,w in [(x+1,y),(x-1,y)]: if 0<=z<H and 0<=w<W and MAP[z][w]==".": if DY[z][w]>DY[x][y] or (DY[z][w]==DY[x][y] and DX[z][w]>DX[x][y]+1): DY[z][w]=DY[x][y] DX[z][w]=DX[x][y]+1 Q.appendleft((z,w)) for z,w in [(x,y+1),(x,y-1)]: if 0<=z<H and 0<=w<W and MAP[z][w]==".": if DY[z][w]>DY[x][y]+1 or (DY[z][w]==DY[x][y] and DX[z][w]>DX[x][y]): DY[z][w]=DY[x][y]+1 DX[z][w]=DX[x][y] Q.append((z,w)) if DY[-1][-1]>1<<50: print("No") else: print("Yes") print(DY[-1][-1],DX[-1][-1])