結果
問題 | No.424 立体迷路 |
ユーザー |
![]() |
提出日時 | 2023-02-08 12:37:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 76 ms / 2,000 ms |
コード長 | 1,584 bytes |
コンパイル時間 | 193 ms |
コンパイル使用メモリ | 82,452 KB |
実行使用メモリ | 73,344 KB |
最終ジャッジ日時 | 2024-07-06 01:22:02 |
合計ジャッジ時間 | 2,594 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
from collections import dequedef bfs(G, s, N):Q = deque([])dist = [-1] * Npar = [-1] * Nsz = [1] * Ndist[s] = 0rev = [0] * Nfor u in G[s]:par[u] = sdist[u] = 1sz[u] += sz[s]Q.append(u)while Q:u = Q.popleft()for v in G[u]:if dist[v] != -1:continueif v < u:rev[v] = rev[u] + 1else:rev[v] = rev[u]dist[v] = dist[u] + 1par[v] = usz[v] += sz[u]Q.append(v)return distdef f(h,w):return h * W + wH, W = map(int, input().split())sx, sy, gx, gy = map(int, input().split())sx, sy, gx, gy = sx - 1, sy - 1, gx - 1, gy - 1B = []for i in range(H):b = list(input())b = list(map(int, b))B.append(b)G = [[] for i in range(H * W)]dx = [1, 0, -1, 0, 2, 0, -2, 0]dy = [0, 1, 0, -1, 0, 2, 0, -2]for i in range(H):for j in range(W):for k in range(8):x = i + dx[k]y = j + dy[k]if x < 0 or x > H - 1 or y < 0 or y > W - 1:continueif k <= 3:if abs(B[i][j] - B[x][y]) <= 1:G[f(i, j)].append(f(x, y))else:if abs(B[i][j] - B[x][y]) == 0:mx, my = i + dx[k]//2, j + dy[k]//2if B[mx][my] < B[x][y]:G[f(i, j)].append(f(x, y))D = bfs(G, f(sx, sy), H * W)print("YES") if D[f(gx, gy)] != -1 else print("NO")