結果
問題 | No.367 ナイトの転身 |
ユーザー |
![]() |
提出日時 | 2021-01-02 02:21:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 294 ms / 2,000 ms |
コード長 | 1,029 bytes |
コンパイル時間 | 374 ms |
コンパイル使用メモリ | 82,128 KB |
実行使用メモリ | 101,888 KB |
最終ジャッジ日時 | 2024-10-11 12:19:47 |
合計ジャッジ時間 | 4,006 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
from collections import deque import sys input = sys.stdin.readline sys.setrecursionlimit(10 ** 7) move = (( (1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1) ), ( (-1, -1), (1, 1), (1, -1), (-1, 1) )) H, W = map(int, input().split()) G = [input().rstrip() for _ in range(H)] for i in range(H): for j in range(W): if G[i][j] == "S": sx, sy = i, j if G[i][j] == "G": gx, gy = i, j inf = 10**9 dist = [[[inf] * 2 for _ in range(W)] for _ in range(H)] dist[sx][sy][0] = 0 que = deque([(sx, sy, 0)]) while que: x, y, f = que.popleft() d = dist[x][y][f] for dx, dy in move[f]: nx = x + dx ny = y + dy if 0 <= nx < H and 0 <= ny < W: nf = f if G[nx][ny] == "R": nf = f ^ 1 if dist[nx][ny][nf] > d + 1: dist[nx][ny][nf] = d + 1 que.append((nx, ny, nf)) ans = min(dist[gx][gy][0], dist[gx][gy][1]) if ans >= inf: ans = -1 print(ans)