Approach
Breadth-first search
For ABC387 D — Snaky Walk, 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 abc387_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 12 grid = [list(input().rstrip()) for _ in range(h)]13 sy, sx = -1, -114 gy, gx = -1, -115 16 for i in range(h):17 for j in range(w):18 if grid[i][j] == "S":19 sy, sx = i, j20 elif grid[i][j] == "G":21 gy, gx = i, j22 23 inf = 10**1824 ans = inf25 dxy = [[(-1, 0), (1, 0)], [(0, -1), (0, 1)]]26 27 for _ in range(2):28 d = deque()29 d.append((sy, sx))30 pending = inf31 dist = [[pending] * w for _ in range(h)]32 dist[sy][sx] = 0 33 34 while d:35 y, x = d.popleft()36 37 if dist[y][x] == pending:38 continue39 40 41 flag = (y + x) % 242 43 for dx, dy in dxy[flag]:44 nx = x + dx45 ny = y + dy46 47 if nx < 0 or nx >= w or ny < 0 or ny >= h:48 continue49 if grid[ny][nx] == "#":50 continue51 if dist[ny][nx] != pending:52 continue53 54 dist[ny][nx] = dist[y][x] + 1 55 d.append((ny, nx))56 57 ans = min(ans, dist[gy][gx])58 59 dxy[0], dxy[1] = dxy[1], dxy[0]60 61 if ans == inf:62 ans = -163 64 print(ans)65 66 67if __name__ == "__main__":68 main()69