結果
問題 | No.367 ナイトの転身 |
ユーザー |
|
提出日時 | 2023-02-13 22:34:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 338 ms / 2,000 ms |
コード長 | 1,070 bytes |
コンパイル時間 | 623 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 111,744 KB |
最終ジャッジ日時 | 2024-07-16 13:40:45 |
合計ジャッジ時間 | 3,742 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
from collections import deque h, w = map(int, input().split()) S = [list(input()) for _ in range(h)] for i in range(h): for j in range(w): if S[i][j] == 'S': si, sj = i, j elif S[i][j] == 'G': gi, gj = i, j INF = 10**18 DP = [[[INF for _ in range(2)] for _ in range(w)] for _ in range(h)] DP[si][sj][0] = 0 Directions = [[(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)], [(1, 1), (1, -1), (-1, -1), (-1, 1)]] Que = deque([(si, sj, 0)]) while Que: ci, cj, idx = Que.popleft() if ci == gi and cj == gj: break cc = DP[ci][cj][idx] for di, dj in Directions[idx]: ni, nj = ci + di, cj + dj if 0 <= ni < h and 0 <= nj < w: if S[ni][nj] == 'R': nidx = idx ^ 1 else: nidx = idx if cc + 1 >= DP[ni][nj][nidx]: continue DP[ni][nj][nidx] = cc + 1 Que.append((ni, nj, nidx)) if min(DP[gi][gj]) == INF: print(-1) else: print(min(DP[gi][gj]))