結果
問題 | No.367 ナイトの転身 |
ユーザー |
![]() |
提出日時 | 2022-12-18 02:40:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 250 ms / 2,000 ms |
コード長 | 1,449 bytes |
コンパイル時間 | 180 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 86,400 KB |
最終ジャッジ日時 | 2024-11-17 10:49:09 |
合計ジャッジ時間 | 4,113 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
from collections import deque H,W=map(int,input().split()) S=[input().strip() for i in range(H)] DIS=[[1<<60]*W for i in range(H)] DIS2=[[1<<60]*W for i in range(H)] for i in range(H): for j in range(W): if S[i][j]=="S": Q=deque([(i,j,0)]) DIS[i][j]=0 while Q: x,y,com=Q.popleft() if com==0: for z,w in [(x+1,y-2),(x+1,y+2),(x-1,y-2),(x-1,y+2),(x+2,y-1),(x+2,y+1),(x-2,y-1),(x-2,y+1)]: if 0<=z<H and 0<=w<W: if S[z][w]=="R": if DIS2[z][w]>DIS[x][y]+1: DIS2[z][w]=DIS[x][y]+1 Q.append((z,w,1)) else: if DIS[z][w]>DIS[x][y]+1: DIS[z][w]=DIS[x][y]+1 Q.append((z,w,0)) else: for z,w in [(x+1,y+1),(x+1,y-1),(x-1,y+1),(x-1,y-1)]: if 0<=z<H and 0<=w<W: if S[z][w]=="R": if DIS[z][w]>DIS2[x][y]+1: DIS[z][w]=DIS2[x][y]+1 Q.append((z,w,0)) else: if DIS2[z][w]>DIS2[x][y]+1: DIS2[z][w]=DIS2[x][y]+1 Q.append((z,w,1)) ANS=1<<60 for i in range(H): for j in range(W): if S[i][j]=="G": ANS=min(ANS,DIS[i][j],DIS2[i][j]) if ANS==1<<60: print(-1) else: print(ANS)