Approach
Breadth-first search
For ABC184 E — Third Avenue, 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
- 77 lines of Python from the credited upstream file abc184_e.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 from collections import deque6 import sys7 8 input = sys.stdin.readline9 10 h, w = map(int, input().split())11 a = [list(input().rstrip()) for _ in range(h)]12 sy, sx = 0, 013 gy, gx = 0, 014 inf = 10 ** 1815 dist = [[inf for _ in range(w)] for __ in range(h)]16 d = deque()17 dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]18 teleport = dict()19 teleport = [[] for _ in range(26)]20 is_used = [False for _ in range(26)]21 22 for i in range(h):23 for j in range(w):24 if a[i][j] == "S":25 sy, sx = i, j26 dist[sy][sx] = 027 d.append((sy, sx))28 elif a[i][j] == "G":29 gy, gx = i, j30 elif a[i][j].islower():31 diff = ord(a[i][j]) - ord("a")32 teleport[diff].append((i, j))33 34 while d:35 y, x = d.popleft()36 37 if y == gy and x == gx:38 print(dist[y][x])39 exit()40 41 for dx, dy in dxy:42 nx = x + dx43 ny = y + dy44 45 if nx < 0 or nx >= w:46 continue47 if ny < 0 or ny >= h:48 continue49 if a[ny][nx] == "#":50 continue51 if dist[ny][nx] != inf:52 continue53 54 dist[ny][nx] = dist[y][x] + 155 d.append((ny, nx))56 57 if a[y][x].islower():58 diff = ord(a[y][x]) - ord("a")59 60 if is_used[diff]:61 continue62 63 for ny, nx in teleport[diff]:64 if dist[ny][nx] != inf:65 continue66 67 dist[ny][nx] = dist[y][x] + 168 d.append((ny, nx))69 70 is_used[diff] = True71 72 print(-1)73 74 75if __name__ == "__main__":76 main()77