2290. Minimum Obstacle Removal to Reach Corner
思路:
(1) Dijkstra's algorithm
把这个矩阵想成一个graph
到有障碍物的格子距离为1
没有障碍物的格子距离为0
请问从grid[0][0]到grid[m-1][n-1]的最短距离
这样想就好了，直接用Dijkstra's algorithm
然后用heap去记录目前离grid[0][0]且还没到过的格子
如果不用heap会TLE
最后的答案就是grid[0][0]到grid[m-1][n-1]的最短距离
(2) BFS
这个就比Dijkstra's algorithm快多了
用两个queue : current、next分别记录这一步可以到达格子和下一步可以到的格子
从[0,0]开始
如果grid[i][j]=0就把它塞到current
反之塞到next
等到current没有东西就进行下一步
并且记录到过的格子
遇到[m-1,n-1]回传当前步数就好
code是BFS的解法
golang code :
func minimumObstacles(grid [][]int) int {
n, m := len(grid), len(grid[0])
visit := make([][]bool, n)
for i := 0; i < n; i++ {
visit[i] = make([]bool, m)
}
direction := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
cur, next := make([][2]int, 1), make([][2]int, 0)
cur[0] = [2]int{0, 0}
visit[0][0] = true
step := 0
for {
for len(cur) > 0 {
idx := cur[0]
cur = cur[1:]
if idx[0] == n-1 && idx[1] == m-1 {
return step
}
for i := 0; i < 4; i++ {
x := idx[0] + direction[i][0]
y := idx[1] + direction[i][1]
if x > -1 && y > -1 && x < n && y < m && !visit[x][y] {
if grid[x][y] == 1 {
next = append(next, [2]int{x, y})
} else {
cur = append(cur, [2]int{x, y})
}
visit[x][y] = true
}
}
}
step++
cur, next = next, cur
}
}
用两个矩阵