Approach
Breadth-first search
For ABC425 D — Ulam-Warburton Automaton, 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
- 70 lines of Python from the credited upstream file abc425_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 s = [list(input().rstrip()) for _ in range(h)]12 13 q = deque()14 inf = 10**1815 dist = [[inf for _ in range(w)] for _ in range(h)]16 17 for i in range(h):18 for j in range(w):19 if s[i][j] == ".":20 continue21 22 q.append((i, j))23 dist[i][j] = 024 25 dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]26 27 while q:28 y, x = q.popleft()29 di = dist[y][x]30 31 for dx, dy in dxy:32 ny, nx = y + dy, x + dx33 34 if not (0 <= ny < h):35 continue36 if not (0 <= nx < w):37 continue38 if dist[ny][nx] != inf:39 continue40 41 count = 042 43 for dx2, dy2 in dxy:44 ny2, nx2 = ny + dy2, nx + dx245 46 if not (0 <= ny2 < h):47 continue48 if not (0 <= nx2 < w):49 continue50 if dist[ny2][nx2] <= di:51 count += 152 continue53 54 if count == 1:55 q.append((ny, nx))56 dist[ny][nx] = dist[y][x] + 157 58 ans = 059 60 for i in range(h):61 for j in range(w):62 if dist[i][j] != inf:63 ans += 164 65 print(ans)66 67 68if __name__ == "__main__":69 main()70