BFS Shortest Path in Dynamic Grid

A navigation system for a Rockstar Games open-world environment models the map as a rectangular grid. Some cells are permanent walls, while other cells become blocked according to a repeating schedule. Implement a time-aware breadth-first search that returns the shortest path from start to goal.

At time 0, the player is at start. During each minute, the player may move to one of the four adjacent cells or wait in place. The destination cell must be inside the grid, not a permanent wall, and not dynamically blocked at the time of arrival. Dynamic blocking schedules repeat after len(dynamic_blocks) phases.

Formal Specification

Implement shortest_dynamic_path(grid, start, goal, dynamic_blocks).

• grid is a non-empty list of equal-length strings. '.' is traversable and '#' is a permanent wall.
• start and goal are integer coordinate lists [row, column].
• dynamic_blocks is a non-empty list of phases. Each phase is a list of coordinate lists blocked during that phase.
• Return a list of coordinate lists representing the shortest path, including start and goal. Return [] if no path exists.

A state is identified by its position and time phase, because the same position may be safe at one time and blocked at another.