Minimum Path Length Through a Grid With One Allowed Cell Conversion
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given an `m x n` grid `grid` where every cell holds either `1` (an **open** cell you may stand on) or `0` (a **blocked** cell).
You start at the top-left cell `(0, 0)` and want to reach the bottom-right cell `(m - 1, n - 1)`. In one **step** you move to a cell that is directly up, down, left, or right of your current cell. You may only stand on open cells.
Before/while you walk, you are allowed to **convert at most one blocked cell (`0`) into an open cell (`1`)**. The conversion may be applied to any single cell in the grid (including the start or end cell), but you may do it **at most once for the entire walk**. A cell that you ever stand on must be open — either originally open, or made open by your one allowed conversion.
Return the **minimum number of steps** needed to travel from `(0, 0)` to `(m - 1, n - 1)`. If it is impossible to reach the destination even after using your single conversion, return `-1`.
### Examples
**Example 1**
```
grid = [[1, 1, 0],
[0, 1, 0],
[0, 1, 1]]
```
Output: `4`
Explanation: The path `(0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2)` uses only originally-open cells and takes 4 steps. No conversion is needed, and 4 is the fewest possible moves.
**Example 2**
```
grid = [[1, 0],
[0, 1]]
```
Output: `2`
Explanation: Both neighbors of the start are blocked. Converting `(0,1)` to open allows the path `(0,0) -> (0,1) -> (1,1)`, which takes 2 steps. (Converting `(1,0)` instead also gives 2 steps.) Without any conversion the destination is unreachable.
**Example 3**
```
grid = [[1, 0, 1],
[0, 0, 0],
[1, 0, 1]]
```
Output: `-1`
Explanation: The four corners are the only open cells. From the start you can use your one conversion to step onto a single neighboring blocked cell, but every cell adjacent to that one (other than already-visited open cells) is also blocked, and your conversion is now spent. The bottom-right corner can never be reached, so the answer is `-1`.
### Constraints
- `m == grid.length`
- `n == grid[i].length`
- `1 <= m, n <= 500`
- `grid[i][j]` is either `0` or `1`.
- Moving onto any cell costs exactly one step; the starting cell `(0, 0)` itself contributes no step.
- At most **one** conversion may be performed for the whole walk.
Quick Answer: This question evaluates a candidate's grasp of shortest-path search on grids, specifically breadth-first search extended with a limited state budget for modifying obstacles. It tests the ability to reason about state-space expansion, where each cell must be tracked alongside how many obstacle conversions remain. Such problems are common in coding interviews to assess practical application of graph traversal beyond textbook BFS.
You are given an `m x n` grid `grid` where every cell holds either `1` (an **open** cell you may stand on) or `0` (a **blocked** cell).
You start at the top-left cell `(0, 0)` and want to reach the bottom-right cell `(m - 1, n - 1)`. In one **step** you move to a cell that is directly up, down, left, or right of your current cell. You may only stand on open cells.
Before/while you walk, you are allowed to **convert at most one blocked cell (`0`) into an open cell (`1`)**. The conversion may be applied to any single cell in the grid (including the start or end cell), but you may do it **at most once for the entire walk**. A cell that you ever stand on must be open — either originally open, or made open by your one allowed conversion.
Return the **minimum number of steps** needed to travel from `(0, 0)` to `(m - 1, n - 1)`. If it is impossible to reach the destination even after using your single conversion, return `-1`.
### Examples
**Example 1**
```
grid = [[1, 1, 0],
[0, 1, 0],
[0, 1, 1]]
```
Output: `4`
Explanation: The path `(0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2)` uses only originally-open cells and takes 4 steps. No conversion is needed, and 4 is the fewest possible moves.
**Example 2**
```
grid = [[1, 0],
[0, 1]]
```
Output: `2`
Explanation: Both neighbors of the start are blocked. Converting `(0,1)` to open allows the path `(0,0) -> (0,1) -> (1,1)`, which takes 2 steps. Without any conversion the destination is unreachable.
**Example 3**
```
grid = [[1, 0, 1],
[0, 0, 0],
[1, 0, 1]]
```
Output: `-1`
Explanation: The four corners are the only open cells. Your single conversion only lets you step onto one blocked cell, and every further move from there is also blocked, so the bottom-right corner can never be reached.
### Constraints
- `m == grid.length`
- `n == grid[i].length`
- `1 <= m, n <= 500`
- `grid[i][j]` is either `0` or `1`.
- Moving onto any cell costs exactly one step; the starting cell `(0, 0)` itself contributes no step.
- At most **one** conversion may be performed for the whole walk.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 500
- grid[i][j] is either 0 or 1
- Moving onto any cell costs exactly one step; the starting cell (0,0) itself contributes no step
- At most one 0 -> 1 conversion may be performed for the whole walk
Examples
Input: ([[1, 1, 0], [0, 1, 0], [0, 1, 1]],)
Expected Output: 4
Explanation: A path using only originally-open cells, (0,0)->(0,1)->(1,1)->(2,1)->(2,2), reaches the goal in 4 steps; no conversion is needed and 4 is optimal.
Input: ([[1, 0], [0, 1]],)
Expected Output: 2
Explanation: Both neighbors of the start are blocked, so the destination is unreachable without help. Converting (0,1) lets you walk (0,0)->(0,1)->(1,1) in 2 steps.
Input: ([[1, 0, 1], [0, 0, 0], [1, 0, 1]],)
Expected Output: -1
Explanation: Only the four corners are open. One conversion lets you step onto a single blocked cell, but every onward move is still blocked, so the bottom-right corner is unreachable.
Input: ([[1]],)
Expected Output: 0
Explanation: The start already equals the destination and is open, so zero steps are required.
Input: ([[0]],)
Expected Output: 0
Explanation: The single cell is both start and destination but blocked; spend the one conversion to stand on it. No moves are made, so the answer is 0 steps.
Input: ([[1, 0, 1], [1, 0, 1], [1, 0, 1]],)
Expected Output: 4
Explanation: The entire middle column is blocked, splitting the open left and right halves. The one allowed conversion must be used to punch through it; the shortest resulting path takes 4 steps.
Hints
- The state is not just your position but also whether you have already spent your one conversion. Model it as (row, col, conversionsUsed) with conversionsUsed in {0, 1}.
- Because every move costs exactly one step, a breadth-first search over these states finds the minimum-step path: the first time you pop the destination cell, its distance is optimal.
- When you step onto an open cell (1), carry the same conversionsUsed. When you step onto a blocked cell (0), you may only do so if conversionsUsed == 0, and the new state has conversionsUsed == 1.
- Edge case: if grid[0][0] == 0, you must use your conversion just to stand on the start, so seed the BFS with conversionsUsed = 1. If the start already equals the destination, the answer is 0.