Approach
Breadth-first search
For ABC308 D — Snuke 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
- 58 lines of Python from the credited upstream file abc308_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 s = [list(input().rstrip()) for _ in range(h)]13 d = deque()14 d.append((0, 0, 0))15 visited = [[False] * w for _ in range(h)]16 dist = [[0] * w for _ in range(h)]17 dist[0][0] = 1 18 dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]19 u = "snuke"20 21 while d:22 y, x, i = d.popleft()23 24 if visited[y][x]:25 continue26 27 if s[y][x] != u[i % 5]:28 continue29 30 visited[y][x] = True31 32 for dx, dy in dxy:33 nx = x + dx34 ny = y + dy35 36 if nx < 0 or nx >= w or ny < 0 or ny >= h:37 continue38 if visited[ny][nx]:39 continue40 if s[ny][nx] != u[(i + 1) % 5]:41 continue42 43 d.append((ny, nx, i + 1))44 dist[ny][nx] = dist[y][x] + 1 45 46 result = visited[h - 1][w - 1]47 48 if result:49 print("Yes")50 else:51 print("No")52 53 54 55 56if __name__ == "__main__":57 main()58