Approach
Breadth-first search
For ABC311 D — Grid Ice Floor, 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
- 51 lines of Python from the credited upstream file abc311_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 n, m = map(int, input().split())11 s = [list(input().rstrip()) for _ in range(n)]12 d = deque()13 d.append((1, 1))14 visited = [[False] * m for _ in range(n)]15 16 stopped = [[False] * m for _ in range(n)]17 dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]18 19 while d:20 y, x = d.popleft()21 22 if stopped[y][x]:23 continue24 25 stopped[y][x] = True26 visited[y][x] = True27 28 for dx, dy in dxy:29 nx, ny = x, y30 31 while s[ny + dy][nx + dx] == ".":32 nx += dx33 ny += dy34 35 if nx < 0 or nx >= m or ny < 0 or ny >= n:36 continue37 if visited[ny][nx]:38 continue39 40 visited[ny][nx] = True41 42 if not stopped[ny][nx]:43 d.append((ny, nx))44 45 ans = sum([sum(row) for row in visited])46 print(ans)47 48 49if __name__ == "__main__":50 main()51