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.