1368. Minimum Cost to Make at Least One Valid Path in a Grid
思路 :
1.
原本我是用min_heap，从左上角开始
把所有可能的方向和cost都丢到min_heap
并且用visited纪录拜访过的cell，每次都先把拜访过的cell pop出来
最后看右下角的cost是多少
2.
后来换一个方法
用dfs去看当前的cost能到达哪些cell
并把能到达的cell和cost用一个queue记录起来
接着从这个queue里面依序取出cell改变方向并且cost+1，再丢到dfs里
看抵达右下角的cost为多少
code 是方法2的
golang code :
func minCost(grid [][]int) int {
n, m := len(grid), len(grid[0])
visited := make([][]bool, n)
direction := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
for i := 0; i < n; i++ {
visited[i] = make([]bool, m)
}
queue := [][3]int{}
var dfs func(i, j, cost int)
dfs = func(i, j, cost int) {
if i > -1 && j > -1 && i < n && j < m && !visited[i][j] {
visited[i][j] = true
next_i, next_j := i+direction[grid[i][j]-1][0], j+direction[grid[i][j]-1][1
]
queue = append(queue, [3]int{i, j, cost})
dfs(next_i, next_j, cost)
}
}
dfs(0, 0, 0)
for {
node := queue[0]
queue = queue[1:]
if node[0] == n-1 && node[1] == m-1 {
return node[2]
}
for k := 0; k < 4; k++ {
next_i, next_j := node[0]+direction[k][0], node[1]+direction[k][1]
dfs(next_i, next_j, node[2]+1)
}
}
}

大师