結果
問題 |
No.2913 二次元距離空間
|
ユーザー |
![]() |
提出日時 | 2024-10-04 23:17:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 130 ms / 2,000 ms |
コード長 | 943 bytes |
コンパイル時間 | 122 ms |
コンパイル使用メモリ | 82,380 KB |
実行使用メモリ | 82,068 KB |
最終ジャッジ日時 | 2024-10-04 23:17:31 |
合計ジャッジ時間 | 2,665 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
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]+1 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])