Approach
Breadth-first search
For ABC460 D — Repeatedly Repainting , 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
- 86 lines of Python from the credited upstream file abc460_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 dxy = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (1, -1), (-1, 1), (1, 1)]13 14 for _ in range(2):15 t = [["." 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 for dx, dy in dxy:23 ny, nx = i + dy, j + dx24 25 if not (0 <= nx < w):26 continue27 if not (0 <= ny < h):28 continue29 if s[ny][nx] == "#":30 continue31 32 t[ny][nx] = "#"33 34 s = t[:]35 36 q = deque()37 inf = 10**18 + 138 dist = [[inf for _ in range(w)] for _ in range(h)]39 40 for i in range(h):41 for j in range(w):42 if s[i][j] == ".":43 continue44 45 q.append((i, j))46 dist[i][j] = 047 48 visited = [[False for _ in range(w)] for _ in range(h)]49 50 while q:51 y, x = q.popleft()52 53 if visited[y][x]:54 continue55 56 visited[y][x] = True57 58 for dx, dy in dxy:59 ny, nx = y + dy, x + dx60 61 if not (0 <= nx < w):62 continue63 if not (0 <= ny < h):64 continue65 if dist[ny][nx] != inf:66 continue67 68 dist[ny][nx] = dist[y][x] + 169 q.append((ny, nx))70 71 ans = [["." for _ in range(w)] for _ in range(h)]72 73 for i in range(h):74 for j in range(w):75 if dist[i][j] % 2 == 1:76 continue77 78 ans[i][j] = "#"79 80 for ans_i in ans:81 print("".join(ans_i))82 83 84if __name__ == "__main__":85 main()86