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
}