Shortest Path With Dynamic Obstacles

An & General Intuition robotic agent navigates a rectangular grid whose walls are permanent and whose obstacles move according to a repeating schedule. At each time step, the agent may move up, down, left, right, or wait. It may not enter a wall or a cell occupied by a dynamic obstacle at the arrival time.

Implement shortest_dynamic_path to return the shortest collision-free path from start to target, including both endpoints. If no path exists, return an empty list.

Formal Specification

• grid is a list of equal-length strings. . is traversable and # is a permanent wall.
• start and target are two-element lists [row, column].
• blocked_by_time is a nonempty list of obstacle-position lists. blocked_by_time[t % P] gives the dynamic obstacles at time t, where P = len(blocked_by_time).
• Each obstacle position is a two-element list [row, column].
• Time starts at 0, and the start cell must be safe at time 0.
• Return a list of positions representing a shortest path, or [] if unreachable.