Approach
Breadth-first search
For ABC400 D — Takahashi the Wall Breaker, 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
- 61 lines of Python from the credited upstream file abc400_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 import sys6 from collections import deque7 8 input = sys.stdin.readline9 10 h, w = map(int, input().split())11 s = [list(input().rstrip()) for _ in range(h)]12 sy, sx, ty, tx = map(lambda x: int(x) - 1, input().split())13 q = deque()14 inf = 10**1815 dist = [[inf for __ in range(w)] for _ in range(h)]16 visited = [[False for __ in range(w)] for _ in range(h)]17 dxy = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (1, -1), (-1, 1), (1, 1)]18 dxy = dxy[:4]19 20 21 def push(y, x, d, cost):22 if not (0 <= y < h and 0 <= x < w):23 return24 if dist[y][x] <= d:25 return26 27 dist[y][x] = d28 29 if cost == 0:30 q.appendleft((y, x))31 else:32 q.append((y, x))33 34 push(sy, sx, 0, 0)35 36 while q:37 cur_y, cur_x = q.popleft()38 39 if visited[cur_y][cur_x]:40 continue41 42 visited[cur_y][cur_x] = True43 44 for dx, dy in dxy:45 ny, nx = cur_y + dy, cur_x + dx46 47 48 if (0 <= ny < h and 0 <= nx < w) and s[ny][nx] == ".":49 push(ny, nx, dist[cur_y][cur_x], 0)50 51 52 push(cur_y + dy, cur_x + dx, dist[cur_y][cur_x] + 1, 1)53 push(cur_y + 2 * dy, cur_x + 2 * dx, dist[cur_y][cur_x] + 1, 1)54 55 ans = dist[ty][tx]56 print(ans)57 58 59if __name__ == "__main__":60 main()61