Approach
Breadth-first search
For ABC383 C — Humidifier 3, 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 abc383_c.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, d = map(int, input().split())11 12 grid = [list(input().rstrip()) for _ in range(h)]13 14 q = deque()15 visited = [[False] * w for _ in range(h)]16 pending = -117 dist = [[pending] * w for _ in range(h)]18 dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]19 20 for i in range(h):21 for j in range(w):22 if grid[i][j] != "H":23 continue24 25 q.append((i, j))26 dist[i][j] = 0 27 28 while q:29 y, x = q.popleft()30 31 if dist[y][x] == pending:32 continue33 34 if visited[y][x]:35 continue36 37 visited[y][x] = True38 39 for dx, dy in dxy:40 nx = x + dx41 ny = y + dy42 43 if nx < 0 or nx >= w or ny < 0 or ny >= h:44 continue45 if visited[ny][nx]:46 continue47 if grid[ny][nx] == "#":48 continue49 if dist[ny][nx] != pending and dist[ny][nx] <= dist[y][x]:50 continue51 if dist[y][x] >= d:52 continue53 54 dist[ny][nx] = dist[y][x] + 1 55 q.append((ny, nx))56 57 ans = 058 59 for i in range(h):60 for j in range(w):61 if dist[i][j] >= 0:62 ans += 163 64 print(ans)65 66 67if __name__ == "__main__":68 main()69