結果
問題 |
No.367 ナイトの転身
|
ユーザー |
|
提出日時 | 2019-11-01 15:42:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 240 ms / 2,000 ms |
コード長 | 1,901 bytes |
コンパイル時間 | 427 ms |
コンパイル使用メモリ | 82,292 KB |
実行使用メモリ | 86,996 KB |
最終ジャッジ日時 | 2024-09-14 22:43:20 |
合計ジャッジ時間 | 4,379 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
import sys input = sys.stdin.readline from collections import deque def bfs(sx, sy): dist = [[[-1] * W for _ in range(H)] for _ in range(2)] dist[0][sx][sy] = 0 q = deque([]) q.append((sx, sy, 0)) while q: cx, cy, f = q.popleft() if f == 0: for nx, ny in [(cx+1, cy+2), (cx+1, cy-2), (cx+2, cy+1), (cx+2, cy-1), (cx-1, cy+2), (cx-1, cy-2), (cx-2, cy+1), (cx-2, cy-1)]: if 0<=nx<H and 0<=ny<W and S[nx][ny] == 'R': if dist[1][nx][ny] == -1: dist[1][nx][ny] = dist[0][cx][cy]+1 q.append((nx, ny, 1)) elif 0<=nx<H and 0<=ny<W and S[nx][ny] != 'R': if dist[0][nx][ny] == -1: dist[0][nx][ny] = dist[0][cx][cy]+1 q.append((nx, ny, 0)) elif f == 1: for nx, ny in [(cx+1, cy+1), (cx+1, cy-1), (cx-1, cy+1), (cx-1, cy-1)]: if 0<=nx<H and 0<=ny<W and S[nx][ny] == 'R': if dist[0][nx][ny] == -1: dist[0][nx][ny] = dist[1][cx][cy]+1 q.append((nx, ny, 0)) elif 0<=nx<H and 0<=ny<W and S[nx][ny] != 'R': if dist[1][nx][ny] == -1: dist[1][nx][ny] = dist[1][cx][cy]+1 q.append((nx, ny, 1)) return dist H, W = map(int, input().split()) S = [input() for _ in range(H)] for i in range(H): for j in range(W): if S[i][j] == 'S': sx, sy = i, j if S[i][j] == 'G': gx, gy = i, j dist = bfs(sx, sy) if dist[0][gx][gy] == -1 and dist[1][gx][gy] == -1: print(-1) elif dist[0][gx][gy] == -1: print(dist[1][gx][gy]) elif dist[1][gx][gy] == -1: print(dist[0][gx][gy]) else: print(min(dist[0][gx][gy], dist[1][gx][gy]))