Approach
Breadth-first search
For ABC421 D — RLE Moving, 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
- 68 lines of Python from the credited upstream file abc421_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 a = [list(input().rstrip()) for _ in range(h)]12 inf = 10**1813 dist = [[[inf for _ in range(w + 10)] for _ in range(h + 10)] for _ in range(2)]14 q = deque()15 16 def push(i, j, state, di):17 if dist[state][i][j] != inf:18 return19 20 dist[state][i][j] = di21 q.append((i, j, state))22 23 sy, sx = -1, -124 25 for i in range(h):26 for j in range(w):27 if a[i][j] == "S":28 sy, sx = i, j29 break30 31 push(sy, sx, 0, 0)32 dxy = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (1, -1), (-1, 1), (1, 1)]33 dxy = dxy[:4]34 35 while q:36 y, x, is_on = q.popleft()37 di = dist[is_on][y][x]38 39 if a[y][x] == "G":40 print(di)41 exit()42 43 for dx, dy in dxy:44 ny, nx = y + dy, x + dx45 nis_on = is_on46 47 if not (0 <= ny < h):48 continue49 if not (0 <= nx < w):50 continue51 if a[ny][nx] == "#":52 continue53 if not nis_on and a[ny][nx] == "x":54 continue55 if nis_on and a[ny][nx] == "o":56 continue57 58 if a[ny][nx] == "?":59 nis_on ^= 160 61 push(ny, nx, nis_on, di + 1)62 63 print(-1)64 65 66if __name__ == "__main__":67 main()68