Approach
Breadth-first search
For ABC176 D — Wizard in Maze, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 78 lines of Python from the credited upstream file abc176_d.py.
- The implementation visibly relies on sequence storage, ordered lookup, work queue.
- No explicit loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4def main():5 from collections import deque6 7 h, w = map(int, input().split())8 sy, sx = map(int, input().split())9 gy, gx = map(int, input().split())10 sy -= 111 sx -= 112 gy -= 113 gx -= 114 s = [list(input()) for _ in range(h)]15 16 dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]17 18 INF = 10 ** 919 dist = [[INF for _ in range(w)] for __ in range(h)]20 visited = [[False for _ in range(w)] for __ in range(h)]21 22 d = deque()23 d.append((sx, sy))24 dist[sy][sx] = 025 visited[sy][sx] = True26 27 while d:28 xi, yi = d.popleft()29 30 for dx, dy in dxy:31 nx = xi + dx32 ny = yi + dy33 34 if nx < 0 or nx >= w:35 continue36 if ny < 0 or ny >= h:37 continue38 if s[ny][nx] == "#":39 continue40 if dist[ny][nx] <= dist[yi][xi]:41 continue42 43 visited[ny][nx] = True44 dist[ny][nx] = dist[yi][xi]45 d.appendleft((nx, ny))46 47 for i in range(-2, 2 + 1):48 for j in range(-2, 2 + 1):49 nx = xi + i50 ny = yi + j51 52 if nx < 0 or nx >= w:53 continue54 if ny < 0 or ny >= h:55 continue56 if s[ny][nx] == "#":57 continue58 if dist[ny][nx] <= dist[yi][xi] + 1:59 continue60 if visited[ny][nx]:61 continue62 63 visited[ny][nx] = True64 dist[ny][nx] = dist[yi][xi] + 165 d.append((nx, ny))66 67 ans = dist[gy][gx]68 69 if ans == INF:70 ans = -171 72 print(ans)73 74 75if __name__ == "__main__":76 77 main()78