1293. Shortest Path in a Grid with Obstacles Elimination #
Problem #
You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.
Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.
Example 1:
Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Output: 6
Explanation:
The shortest path without eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
Example 2:
Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
Output: -1
Explanation: We need to eliminate at least two obstacles to find such a walk.
Constraints:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 40
- 1 <= k <= m * n
- grid[i][j] is either 0 or 1.
- grid[0][0] == grid[m - 1][n - 1] == 0
Problem Summary #
Given an m * n grid, each cell is either 0 (empty) or 1 (obstacle). In each step, you can move up, down, left, or right in empty cells.
If you can eliminate at most k obstacles, find the shortest path from the upper-left corner (0, 0) to the lower-right corner (m-1, n-1), and return the number of steps required to take that path. If no such path can be found, return -1.
Solution Approach #
Use BFS to traverse the board. Compared with an ordinary reachability problem, this problem has an additional obstacle constraint. This is not difficult either. When expanding from each point in the four surrounding directions, if an obstacle is encountered, count this obstacle first; when the total accumulated number of obstacles is less than K, continue traversing from this obstacle cell. If no obstacle is encountered, check whether the current accumulated number of obstacles is already less than K; if it is less than K, continue traversing. If it is greater than K, terminate this round of traversal.
Code #
var dir = [][]int{
{-1, 0},
{0, 1},
{1, 0},
{0, -1},
}
type pos struct {
x, y int
obstacle int
step int
}
func shortestPath(grid [][]int, k int) int {
queue, m, n := []pos{}, len(grid), len(grid[0])
visitor := make([][][]int, m)
if len(grid) == 1 && len(grid[0]) == 1 {
return 0
}
for i := 0; i < m; i++ {
visitor[i] = make([][]int, n)
for j := 0; j < n; j++ {
visitor[i][j] = make([]int, k+1)
}
}
visitor[0][0][0] = 1
queue = append(queue, pos{x: 0, y: 0, obstacle: 0, step: 0})
for len(queue) > 0 {
size := len(queue)
for size > 0 {
size--
node := queue[0]
queue = queue[1:]
for i := 0; i < len(dir); i++ {
newX := node.x + dir[i][0]
newY := node.y + dir[i][1]
if newX == m-1 && newY == n-1 {
if node.obstacle != 0 {
if node.obstacle <= k {
return node.step + 1
} else {
continue
}
}
return node.step + 1
}
if isInBoard(grid, newX, newY) {
if grid[newX][newY] == 1 {
if node.obstacle+1 <= k && visitor[newX][newY][node.obstacle+1] != 1 {
queue = append(queue, pos{x: newX, y: newY, obstacle: node.obstacle + 1, step: node.step + 1})
visitor[newX][newY][node.obstacle+1] = 1
}
} else {
if node.obstacle <= k && visitor[newX][newY][node.obstacle] != 1 {
queue = append(queue, pos{x: newX, y: newY, obstacle: node.obstacle, step: node.step + 1})
visitor[newX][newY][node.obstacle] = 1
}
}
}
}
}
}
return -1
}
func isInBoard(board [][]int, x, y int) bool {
return x >= 0 && x < len(board) && y >= 0 && y < len(board[0])
}
中文