Find shortest path on infinite grid

You are given an infinite 2D grid with integer coordinates. From a cell (x, y) you may move in 4 directions (North/South/East/West) by 1 cell per move.

You are given:

• start = (sx, sy)
• goal = (gx, gy)
• A finite set of static barriers blocked, where each coordinate in blocked is permanently impassable.

Part 1 (static obstacles)

Return any one shortest valid path from start to goal as a list of coordinates (or directions). If no path exists, return “unreachable”.

Important: the grid is infinite. A naive BFS that expands forever must be avoided; your algorithm should terminate even when goal is unreachable (e.g., goal is fully enclosed by barriers).

Part 2 (moving parades)

Now, in addition to blocked, you are given a list of moving obstacles called parades. Each parade has:

• an initial position (px, py) at time t = 0
• a direction in {N, S, E, W}
• it moves one cell in its direction every 2 seconds (i.e., it changes position at times t = 2, 4, 6, ...; it stays in place at t = 0, 1, then moves for t = 2, 3, etc.).

Rules:

• You still move once per second (at integer times). Optionally, you may also wait in place for 1 second.
• You may never be on a cell that is a static barrier.
• You may never be on a cell occupied by any parade at that time. If a move would place you onto a parade’s position at time t+1, that move is invalid.

Return any minimum-time valid path from start at t=0 to goal (with timestamps implied by step index), or “unreachable”.

As in Part 1, the grid is infinite; ensure your approach does not run forever when the destination cannot be reached.

Part 1: Shortest Path on an Infinite Grid with Static Barriers

You are given an infinite 2D grid of integer coordinates. From a cell (x, y), you may move one step per move in 4 directions: East, North, West, or South. You are also given a finite set of blocked cells that cannot be entered. Write a function that returns one shortest valid path from start to goal as a list of coordinates, including both endpoints. If no valid path exists, return "unreachable". Because the grid is infinite, your algorithm must avoid an unbounded BFS that can run forever on unreachable cases.

Constraints

• Coordinates are integers.
• 0 <= len(blocked) <= 2000
• Let R be the axis-aligned rectangle containing start, goal, and all blocked cells. The area of R expanded by 1 cell in every direction is at most 200000.
• If multiple shortest paths exist, any one is acceptable.

Examples

Example 1

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

Explanation: No barriers. The Manhattan-distance path is shortest.

Example 2

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

Explanation: The direct route is blocked, so the shortest path goes around the obstacle.

Hints

1. A shortest path never needs to wander arbitrarily far away from the rectangle containing start, goal, and the blocked cells.
2. Use BFS for shortest path in an unweighted grid, and store parent pointers to reconstruct the path.

Part 2: Minimum-Time Path with Moving Parades

You are given an infinite 2D grid of integer coordinates. From a cell (x, y), you may move once per second in 4 directions: East, North, West, or South. You may also wait in place for 1 second. Some cells are statically blocked forever. In addition, there are moving obstacles called parades. Each parade is given as (px, py, dir), where dir is one of 'N', 'S', 'E', 'W'. At integer time t, the parade occupies the cell reached after floor(t / 2) steps in its direction from its initial position. That means it stays at its initial cell at t = 0 and t = 1, then moves one cell at t = 2 and stays there at t = 2 and t = 3, and so on. You may never be on a blocked cell, and you may never be on a cell occupied by a parade at that time. Return one minimum-time valid path from start at t = 0 to goal, as a list of coordinates whose indices are the times. Repeated coordinates represent waiting. If no valid path exists, return "unreachable". Your algorithm must terminate even when the answer is unreachable.

Constraints

• Coordinates are integers.
• 0 <= len(blocked) <= 200
• 0 <= len(parades) <= 25
• Let B be the rectangle containing start, goal, and all blocked cells, expanded by len(parades) + 1 cells in each direction. The area of B is at most 20000.
• If H is the latest time any parade occupies a cell of B, then H <= 500.
• If multiple minimum-time paths exist, any one is acceptable.

Examples

Example 1

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

Explanation: No parades. This reduces to the static-obstacle case.

Example 2

Input: ((0, 0), (2, 0), [], [(1, 0, 'N')])
Output: [(0, 0), (0, 0), (1, 0), (2, 0)]

Explanation: The cell (1, 0) is occupied at t = 0 and t = 1, so waiting once is optimal.

Hints

1. A state is not just (x, y). Time matters, so think in terms of (x, y, t).
2. Because the number of parades is finite, inside a fixed finite search box every parade eventually leaves that box. This gives a finite time horizon for BFS.