Approach
Breadth-first search
For ABC213 E — Stronger Takahashi, 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
- 69 lines of Python from the credited upstream file abc213_e.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 s = [list(input()) for _ in range(h)]9 inf = 10 ** 1010 costs = [[inf for _ in range(w)] for _ in range(h)]11 costs[0][0] = 012 visited = [[False for _ in range(w)] for _ in range(h)]13 dxy = [(0, 1), (1, 0), (0, -1), (-1, 0)]14 d = deque()15 d.append((0, 0))16 17 while d:18 cur_y, cur_x = d.popleft()19 20 if visited[cur_y][cur_x]:21 continue22 23 visited[cur_y][cur_x] = True24 cost = costs[cur_y][cur_x]25 26 27 for dx, dy in dxy:28 nx = cur_x + dx29 ny = cur_y + dy30 31 if nx < 0 or nx >= w:32 continue33 if ny < 0 or ny >= h:34 continue35 if s[ny][nx] == '#':36 continue 37 if costs[ny][nx] <= cost:38 continue39 40 costs[ny][nx] = cost41 d.appendleft((ny, nx))42 43 44 for dx2 in range(-2, 3):45 for dy2 in range(-2, 3):46 47 if abs(dy2) + abs(dx2) > 3:48 continue49 50 nx2 = cur_x + dx251 ny2 = cur_y + dy252 53 if nx2 < 0 or nx2 >= w:54 continue55 if ny2 < 0 or ny2 >= h:56 continue57 if costs[ny2][nx2] <= cost + 1:58 continue59 60 costs[ny2][nx2] = cost + 161 d.append((ny2, nx2))62 63 64 print(costs[h - 1][w - 1])65 66 67if __name__ == "__main__":68 main()69