結果
問題 |
No.367 ナイトの転身
|
ユーザー |
![]() |
提出日時 | 2022-12-18 02:39:52 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,449 bytes |
コンパイル時間 | 89 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 22,528 KB |
最終ジャッジ日時 | 2024-11-17 10:48:59 |
合計ジャッジ時間 | 10,308 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 TLE * 1 |
ソースコード
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)