Approach
Breadth-first search
For ABC436 D — Teleport 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
- 82 lines of Python from the credited upstream file abc436_d.py.
- The implementation visibly relies on sequence storage, hash lookup, 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 7 from collections import deque, defaultdict8 9 input = sys.stdin.readline10 11 h, w = map(int, input().split())12 13 grid = [list(input().rstrip()) for _ in range(h)]14 15 d = defaultdict(list)16 17 for i in range(h):18 for j in range(w):19 cur = grid[i][j]20 21 if not cur.islower():22 continue23 24 d[cur].append((i, j))25 26 sy, sx = 0, 027 pending = -128 q = deque()29 q.append((sy, sx))30 dist = [[pending] * w for _ in range(h)]31 dist[sy][sx] = 0 32 visited = [[False] * w for _ in range(h)]33 dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]34 used = set()35 36 while q:37 y, x = q.popleft()38 39 if dist[y][x] == pending:40 continue41 if visited[y][x]:42 continue43 44 visited[y][x] = True45 46 cur = grid[y][x]47 48 if cur.islower() and cur not in used:49 for ny, nx in d[cur]:50 if visited[ny][nx]:51 continue52 if dist[ny][nx] != pending and dist[ny][nx] <= dist[y][x]:53 continue54 55 dist[ny][nx] = dist[y][x] + 156 q.append((ny, nx))57 58 used.add(cur)59 60 for dx, dy in dxy:61 nx = x + dx62 ny = y + dy63 64 if nx < 0 or nx >= w or ny < 0 or ny >= h:65 continue66 if visited[ny][nx]:67 continue68 if grid[ny][nx] == "#":69 continue70 if dist[ny][nx] != pending and dist[ny][nx] <= dist[y][x]:71 continue72 73 dist[ny][nx] = dist[y][x] + 1 74 q.append((ny, nx))75 76 ans = dist[h - 1][w - 1]77 print(ans)78 79 80if __name__ == "__main__":81 main()82