Find shortest path on infinite grid

Consider an infinite grid whose cells are all integer coordinate pairs. From a cell (x, y), one move changes either the x-coordinate or the y-coordinate by exactly 1. You are given start = (sx, sy), goal = (gx, gy), and a finite set blocked of permanently impassable cells. Return one shortest path from start to goal as a list of coordinates, including both endpoints. If no such route exists, return "unreachable".

Because the grid is unbounded, the search must not expand forever when the destination is closed off by barriers. If several shortest routes exist, any one is accepted.

Example 1:

Input: start = (1, 2), goal = (4, 5), blocked = []

Output: [(1, 2), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4), (4, 5)]

Explanation: With no blocked cells, this is a Manhattan shortest route of 6 steps.

Example 2:

Input: start = (0, 0), goal = (3, 0), blocked = [(1, 0), (2, 0)]

Output: [(0, 0), (0, 1), (1, 1), (2, 1), (3, 1), (3, 0)]

Explanation: The two adjacent barriers block the direct row, so the shortest valid path detours above them in 5 moves.

Example 3:

Input: start = (0, 0), goal = (2, 2), blocked = [(1, 2), (3, 2), (2, 1), (2, 3)]

Output: "unreachable"

Explanation: All four orthogonal neighbors of the goal are blocked, so it cannot be entered.

Constraints:

• Coordinates are integers.
• $0 \le \text{len}(blocked) \le 3000$
• Let $R$ be the smallest axis-aligned rectangle containing start, goal, and every blocked cell. After expanding $R$ by one cell in each of the four cardinal directions, its area is at most $250{,}000$.

Now assume there are also moving obstacles called parades. A parade is represented by (px, py, dir), where dir is one of 'N', 'S', 'E', or 'W'. At time $t=0$ it is at (px, py). For every integer time $t$, it occupies the cell reached after making $\lfloor t/2 \rfloor$ one-cell moves in its chosen direction from that start. Thus it stays at its start for $t=0$ and $t=1$, moves once at $t=2$ and stays there for $t=2$ and $t=3$, moves again at $t=4$, and so on.

You still make one orthogonal move per second, and you may also wait for one second. At any integer time, you cannot share a cell with a static barrier or with any parade's current cell. A transition into a cell at time $t+1$ is invalid if that same cell is occupied at time $t+1$.

Return a minimum-time legal path from start at time $0$ to goal, as a list of coordinates whose indices are the times. A repeated coordinate denotes waiting. If no legal path exists, return "unreachable". The search must terminate even when the goal is unreachable. If there are multiple minimum-time paths, any one is accepted.

Example 1:

Input: start = (2, 0), goal = (5, 1), blocked = [(4, 0)], parades = []

Output: [(2, 0), (2, 1), (3, 1), (4, 1), (5, 1)]

Explanation: With no moving obstacles, this reduces to the static case and requires 4 moves.

Example 2:

Input: start = (5, 5), goal = (8, 5), blocked = [], parades = [(6, 5, 'N')]

Output: [(5, 5), (5, 5), (6, 5), (7, 5), (8, 5)]

Explanation: The parade occupies (6, 5) at times 0 and 1, so the agent waits once; by time 2, the parade has advanced one cell north.

Constraints:

• Coordinates are integers.
• $0 \le \text{len}(blocked) \le 250$
• $0 \le \text{len}(parades) \le 30$
• Let $B$ be the smallest axis-aligned rectangle containing start, goal, and all blocked cells, expanded by $\text{len}(parades) + 1$ cells in each of the four directions. The area of $B$ is at most $25{,}000$.
• If $H$ is the latest integer time at which any parade occupies a cell inside $B$, then $H \le 600$.