Shortest Path in a Grid with Blocked Cells
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Shortest Path in a Grid with Blocked Cells
You are given an `m x n` grid that represents a floor plan. Each cell is one of:
- `0` — an open cell you can walk through.
- `1` — a wall: this cell is blocked and can never be entered.
You start at the top-left cell `(0, 0)` and want to reach the bottom-right cell `(m - 1, n - 1)`. From any cell you may move one step **up, down, left, or right** (no diagonal moves) into an adjacent open cell that lies inside the grid. You may never step onto a wall and you may never leave the grid.
Return the length of the **shortest path** from `(0, 0)` to `(m - 1, n - 1)`, measured as the number of moves (steps) taken. If no such path exists — for example, because walls fully disconnect the start from the destination — return `-1`.
Both the start cell `(0, 0)` and the destination cell `(m - 1, n - 1)` are guaranteed to be open (value `0`) unless stated otherwise by the constraints below; if either one is a wall, no path exists and you must return `-1`.
## Examples
**Example 1**
```
grid = [
[0, 0, 1],
[1, 0, 1],
[1, 0, 0]
]
```
Output: `4`
One shortest route is `(0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2)`, which is 4 moves.
**Example 2**
```
grid = [
[0, 1],
[1, 0]
]
```
Output: `-1`
The destination `(1,1)` is open, but every route to it is cut off by walls, so it is unreachable.
**Example 3**
```
grid = [
[0]
]
```
Output: `0`
The start cell is also the destination, so zero moves are required.
## Constraints
- `m == grid.length`
- `n == grid[0].length`
- `1 <= m, n <= 1000`
- Each `grid[i][j]` is either `0` or `1`.
- The grid may contain up to `10^6` cells in total.
- A single cell (`m == n == 1`) with value `0` is a valid input whose answer is `0`.
## Required Output
Return a single integer: the minimum number of moves on a shortest path, or `-1` if the destination cannot be reached.
Quick Answer: This question tests a candidate's practical grasp of graph traversal algorithms applied to 2D grid problems, specifically BFS for unweighted shortest-path search. It is a standard coding interview problem that assesses the ability to model spatial constraints, handle edge cases like disconnected graphs, and reason about time and space complexity at scale.
You are given an `m x n` grid that represents a floor plan. Each cell is one of:
- `0` — an open cell you can walk through.
- `1` — a wall: this cell is blocked and can never be entered.
You start at the top-left cell `(0, 0)` and want to reach the bottom-right cell `(m - 1, n - 1)`. From any cell you may move one step **up, down, left, or right** (no diagonal moves) into an adjacent open cell that lies inside the grid. You may never step onto a wall and you may never leave the grid.
Return the length of the **shortest path** from `(0, 0)` to `(m - 1, n - 1)`, measured as the number of moves (steps) taken. If no such path exists — for example, because walls fully disconnect the start from the destination — return `-1`.
If either the start cell `(0, 0)` or the destination cell `(m - 1, n - 1)` is a wall, no path exists and you must return `-1`. A single open cell (`m == n == 1`, value `0`) has answer `0` because the start is already the destination.
**Example 1**
```
grid = [
[0, 0, 1],
[1, 0, 1],
[1, 0, 0]
]
```
Output: `4`. One shortest route is `(0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2)`.
**Example 2**
```
grid = [
[0, 1],
[1, 0]
]
```
Output: `-1`. The destination is open but cut off by walls.
**Example 3**
```
grid = [
[0]
]
```
Output: `0`. Start equals destination.
Constraints
- m == grid.length
- n == grid[0].length
- 1 <= m, n <= 1000
- Each grid[i][j] is either 0 or 1
- The grid may contain up to 10^6 cells in total
- A single cell (m == n == 1) with value 0 is valid and its answer is 0
Examples
Input: ([[0, 0, 1], [1, 0, 1], [1, 0, 0]],)
Expected Output: 4
Explanation: Route (0,0)->(0,1)->(1,1)->(2,1)->(2,2) takes 4 moves; no shorter route exists.
Input: ([[0, 1], [1, 0]],)
Expected Output: -1
Explanation: Destination (1,1) is open but walls at (0,1) and (1,0) cut off every route.
Input: ([[0]],)
Expected Output: 0
Explanation: Start equals destination, so zero moves are needed.
Input: ([[1]],)
Expected Output: -1
Explanation: The single cell is a wall, so start (and destination) is blocked — no path.
Input: ([[0, 0, 0], [0, 0, 0], [0, 0, 0]],)
Expected Output: 4
Explanation: On a fully open 3x3 grid the shortest corner-to-corner path is (m-1)+(n-1)=2+2=4 moves.
Input: ([[0, 0, 0, 0, 0]],)
Expected Output: 4
Explanation: A single open row of width 5 needs 4 rightward moves.
Input: ([[0], [0], [1], [0]],)
Expected Output: -1
Explanation: The wall at row 2 in a single column disconnects the start from the destination.
Input: ([[0, 1, 0], [0, 0, 0], [0, 1, 0]],)
Expected Output: 4
Explanation: Walls force a detour through the middle row; the shortest route still takes 4 moves.
Hints
- Shortest path with uniform (unit) edge weights on an unweighted grid is exactly what breadth-first search (BFS) solves — the first time you reach the destination, that distance is the minimum.
- Track visited cells so you never revisit one; mark a cell visited when you enqueue it (not when you dequeue) to avoid pushing duplicates.
- Handle the special cases up front: if start or destination is a wall return -1, and if the grid is a single open cell the answer is 0.
- From each cell explore the four orthogonal neighbors; skip any that fall outside the grid, are walls, or have already been visited.