Minimum Moves on a Grid with k-Cell Jumps
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an `m x n` grid. Each cell is either open or blocked:
- `grid[i][j] = 0` means the cell is open.
- `grid[i][j] = 1` means the cell is blocked.
You start at cell `(sr, sc)` and want to reach the target cell `(tr, tc)`. Both the start and the target are guaranteed to be open.
In a single **move** you:
1. Choose one of the four cardinal directions: up, down, left, or right.
2. Travel between `1` and `k` cells (inclusive) in a straight line in that direction.
A move is only legal if **every** cell along the path of the move (including the cell you land on) stays inside the grid and is open. You may not move off the grid, and you may not pass through or stop on a blocked cell.
Return the **minimum number of moves** needed to reach the target from the start. If the target cannot be reached, return `-1`.
### Input
- `grid`: a 2D integer array of size `m x n` with values `0` (open) or `1` (blocked).
- `sr`, `sc`: integer coordinates of the start cell.
- `tr`, `tc`: integer coordinates of the target cell.
- `k`: the maximum number of cells you may travel in a single move.
### Output
- An integer: the minimum number of moves, or `-1` if the target is unreachable.
### Constraints
- `1 <= m, n <= 1000`
- `grid[i][j]` is `0` or `1`
- `0 <= sr, tr < m` and `0 <= sc, tc < n`
- `grid[sr][sc] == 0` and `grid[tr][tc] == 0`
- `1 <= k <= max(m, n)`
### Example 1
```
grid = [[0, 0, 0],
[0, 1, 0],
[0, 0, 0]]
sr = 0, sc = 0, tr = 2, tc = 2, k = 2
```
Output: `2`
Explanation: Move right 2 cells from `(0,0)` to `(0,2)` (passing through the open cell `(0,1)`), then move down 2 cells from `(0,2)` to `(2,2)`. Two moves total. With `k = 1` the same trip would require 4 moves while routing around the blocked center cell.
### Example 2
```
grid = [[0, 1, 0],
[1, 1, 0],
[0, 0, 0]]
sr = 0, sc = 0, tr = 0, tc = 2, k = 3
```
Output: `-1`
Explanation: The start cell `(0,0)` is walled off from the rest of the grid by blocked cells in every reachable direction, so the target is unreachable.
### Example 3
```
grid = [[0, 0, 0, 0]]
sr = 0, sc = 0, tr = 0, tc = 3, k = 3
```
Output: `1`
Explanation: A single move travels 3 cells to the right, from `(0,0)` directly to `(0,3)`.
Quick Answer: This question evaluates a candidate's ability to apply shortest-path search on a grid with a non-standard movement rule allowing multi-cell moves. It tests breadth-first search and careful boundary/obstacle handling, commonly asked in coding interviews to gauge practical algorithmic problem-solving under added constraints.
You are given an `m x n` grid. Each cell is either open (`grid[i][j] = 0`) or blocked (`grid[i][j] = 1`).
You start at cell `(sr, sc)` and want to reach the target cell `(tr, tc)`. Both the start and the target are guaranteed to be open.
In a single **move** you:
1. Choose one of the four cardinal directions: up, down, left, or right.
2. Travel between `1` and `k` cells (inclusive) in a straight line in that direction.
A move is only legal if **every** cell along the path of the move (including the cell you land on) stays inside the grid and is open. You may not move off the grid, and you may not pass through or stop on a blocked cell.
Return the **minimum number of moves** needed to reach the target from the start, or `-1` if the target is unreachable.
Implement `solution(grid, sr, sc, tr, tc, k)`.
**Constraints**
- `1 <= m, n <= 1000`
- `grid[i][j]` is `0` or `1`
- `0 <= sr, tr < m` and `0 <= sc, tc < n`
- `grid[sr][sc] == 0` and `grid[tr][tc] == 0`
- `1 <= k <= max(m, n)`
Constraints
- 1 <= m, n <= 1000
- grid[i][j] is 0 (open) or 1 (blocked)
- 0 <= sr, tr < m and 0 <= sc, tc < n
- grid[sr][sc] == 0 and grid[tr][tc] == 0
- 1 <= k <= max(m, n)
Examples
Input: ([[0,0,0],[0,1,0],[0,0,0]], 0, 0, 2, 2, 2)
Expected Output: 2
Explanation: Right 2 cells (0,0)->(0,2) passing through open (0,1), then down 2 cells (0,2)->(2,2). Two moves.
Input: ([[0,1,0],[1,1,0],[0,0,0]], 0, 0, 0, 2, 3)
Expected Output: -1
Explanation: Start (0,0) is walled off: (0,1) and (1,0) are both blocked, so no legal move exists and the target is unreachable.
Input: ([[0,0,0,0]], 0, 0, 0, 3, 3)
Expected Output: 1
Explanation: A single rightward move of 3 cells goes directly from (0,0) to (0,3).
Input: ([[0]], 0, 0, 0, 0, 1)
Expected Output: 0
Explanation: Start equals target, so zero moves are needed.
Input: ([[0,0,0],[0,1,0],[0,0,0]], 0, 0, 2, 2, 1)
Expected Output: 4
Explanation: With k=1 you must route around the blocked center: (0,0)->(1,0)->(2,0)->(2,1)->(2,2), four moves.
Input: ([[0,1,0],[0,1,0],[0,1,0]], 0, 0, 0, 2, 3)
Expected Output: -1
Explanation: Column 1 is a solid wall separating the left column from the right, so the target on the right is unreachable.
Hints
- Every move costs exactly 1 regardless of how far you jump, so this is an unweighted shortest-path problem: run BFS where 'neighbors' are all cells reachable in one legal move.
- From a cell, expand in each of the 4 directions one step at a time up to k steps, breaking the moment you leave the grid or hit a blocked cell — you cannot pass through or stop on a blocked cell.
- A cell that was already reached at an equal-or-smaller distance should not stop your directional sweep: keep going so farther still-unvisited open cells in the same line get their distance set. Only stop on a wall or the edge.