Re: [閒聊] 每日leetcode
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)
}
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.252.255 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1737259536.A.46F.html
推
01/19 12:05,
10月前
, 1F
01/19 12:05, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1293 之 1552 篇)：