You are given an m x n grid. Each cell is either empty or blocked by an obstacle. From any empty cell, you may move in one of four directions: left, right, up, or down.
In one step, you may jump from 1 to k cells in the chosen direction. Every cell crossed during the jump, including the landing cell, must be inside the grid and must not be an obstacle.
Return the minimum number of steps required to reach the destination cell from the source cell. If the destination cannot be reached, return -1.
Method Signature
int minimumSteps(List<String> grid, int k, int sourceRow, int sourceColumn, int destinationRow, int destinationColumn)
grid represents the grid, where '.' means an empty cell and '#' means an obstacle.k is the maximum number of cells that can be jumped in one step.sourceRow and sourceColumn represent the starting cell.destinationRow and destinationColumn represent the target cell.- The method returns the minimum number of valid jumps needed to reach the destination.
Movement Rules
- In one step, choose exactly one direction among left, right, up, and down.
- You may move any distance
d such that 1 ≤ d ≤ k.
- A jump is valid only if all crossed cells are empty.
- You cannot move outside the grid.
- You cannot jump over an obstacle.
- If the source cell is already the destination cell, return
0.
Constraints
1 ≤ grid.size() ≤ 1,0001 ≤ grid.get(i).length() ≤ 1,000- All rows in
grid have the same length.
1 ≤ k ≤ 1,0000 ≤ sourceRow < grid.size()0 ≤ destinationRow < grid.size()0 ≤ sourceColumn < grid.get(0).length()0 ≤ destinationColumn < grid.get(0).length()grid.get(sourceRow).charAt(sourceColumn) = '.'grid.get(destinationRow).charAt(destinationColumn) = '.'- Each character in
grid is either '.' or '#'.
- All input values are valid.
Examples
Example 1
minimumSteps(grid = List.of("....", ".##.", "...."), k = 2, sourceRow = 0, sourceColumn = 0, destinationRow = 2, destinationColumn = 3)
Output: 3
Explanation: One shortest path is from (0,0) to (0,2), then to (0,3), then to (2,3).
Example 2
minimumSteps(grid = List.of("...", "...", "..."), k = 3, sourceRow = 0, sourceColumn = 0, destinationRow = 2, destinationColumn = 2)
Output: 2
Explanation: Jump from (0,0) to (0,2), then from (0,2) to (2,2).
Example 3
minimumSteps(grid = List.of(".#.", "###", ".#."), k = 2, sourceRow = 0, sourceColumn = 0, destinationRow = 2, destinationColumn = 2)
Output: -1
Explanation: The destination cannot be reached because obstacles block all possible paths.
Example 4
minimumSteps(grid = List.of("..", ".."), k = 1, sourceRow = 1, sourceColumn = 1, destinationRow = 1, destinationColumn = 1)
Output: 0
Explanation: The source cell is already the destination cell.