Shortest Path on a Grid with Alternating Move Directions
You have an $n \times n$ grid where some cells are obstacles. Movement rules alternate by time step:
- At **even** time steps ($t = 0, 2, 4, \ldots$), you may only move **vertically** (up or down by one cell).
- At **odd** time steps ($t = 1, 3, 5, \ldots$), you may only move **horizontally** (left or right by one cell).
You may also choose to **stay in place** at any time step (this still advances the clock by 1).
You start at cell $(1, 1)$ at time $t = 0$ and want to reach cell $(n, n)$.
1. Define a state space that accounts for position and time parity. How large is this state space?
2. Design an $O(n^2)$ algorithm to compute the minimum time to reach $(n, n)$, or report that it is unreachable.
3. Prove that BFS on your state space returns the correct shortest-path answer.
**Constraints:**
-
\leq n \leq 1000$
- The grid is given as an $n \times n$ binary matrix where $0$ = free cell and $ = obstacle.
- $(1,1)$ and $(n,n)$ are always free.
**Example 1:**
```
Input: grid = [[0,0,0],
[0,1,0],
[0,0,0]]
Output: 6
Explanation (0-indexed cells; each move advances the clock by 1):
t=0 (even, vertical): (0,0) -> (1,0)
t=1 (odd, horizontal): (1,0) -> (1,0) [stay; obstacle at (1,1)]
t=2 (even, vertical): (1,0) -> (2,0)
t=3 (odd, horizontal): (2,0) -> (2,1)
t=4 (even, vertical): (2,1) -> (2,1) [stay]
t=5 (odd, horizontal): (2,1) -> (2,2)
The target (2,2) is first occupied after 6 moves, so the minimum time is 6.
```
**Example 2:**
```
Input: grid = [[0,0],
[0,0]]
Output: 2
Explanation (0-indexed):
t=0 (even, vertical): (0,0) -> (1,0)
t=1 (odd, horizontal): (1,0) -> (1,1)
(1,1) is (n,n) for n=2, reached after 2 moves. Minimum time = 2.
```
Open the full interactive solver, hints, and worked solution →