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
}
}
用兩個矩陣