2577. Minimum Time to Visit a Cell In a Grid
思路:
這題的重點在於走過的格子是可以重複走的
所以只有當[1,0],[0,1]的值都 >1 的情況才要回-1
然後就是heap + bfs
用heap維護目前到哪個格子要花費的時間最短
從一個格子i到另外一個格子j([x,y])要花費的時間為
max(到i花費的時間+1，grid[x][y]+k)
如果到i花費的時間跟grid[x][y]同為奇數或偶數
k=1
反之k=0
再把從i到j花費的時間push到heap裡
最後看第一次到終點的時間是多少就是答案了
記得要記錄走過那些點，不要重複走
ｇｏｌａｎｇ ｃｏｄｅ ：
type min_heap struct {
nodes []int
distnace []int
}
func (this min_heap) Len() int { return len(this.nodes) }
func (this min_heap) Swap(i, j int) { this.nodes[i], this.nodes[j] = this.
nodes[j], this.nodes[i] }
func (this min_heap) Less(i, j int) bool {
return this.distnace[this.nodes[i]] < this.distnace[this.nodes[j]]
}
func (this *min_heap) Push(x interface{}) { (*this).nodes = append((*this).
nodes, x.(int)) }
func (this *min_heap) Pop() interface{} {
n := len((*this).nodes)
res := (*this).nodes[n-1]
(*this).nodes = (*this).nodes[:n-1]
return res
}
func minimumTime(grid [][]int) int {
if grid[0][1] > 1 && grid[1][0] > 1 {
return -1
}
n, m := len(grid), len(grid[0])
distance := make([]int, n*m)
visit := make([]bool, n*m)
direction := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
h := min_heap{[]int{}, distance}
heap.Push(&h, 0)
visit[0] = true
for {
node := heap.Pop(&h).(int)
old_x, old_y := node/m, node%m
for i := 0; i < 4; i++ {
x, y := old_x+direction[i][0], old_y+direction[i][1]
newnode := x*m + y
if x < n && y < m && x > -1 && y > -1 && !visit[newnode] {
visit[newnode] = true
var tmp int
if grid[x][y]&1 == distance[node]&1 {
tmp = max(grid[x][y]+1, distance[node]+1)
} else {
tmp = max(grid[x][y], distance[node]+1)
}
if x == n-1 && y == m-1 {
return tmp
}
distance[newnode] = tmp
heap.Push(&h, newnode)
}
}
}
return -1
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.34.174 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1732895451.A.314.html