medium都这么难的吗?
难怪我进不了姑姑鲁
2812. Find the Safest Path in a Grid
有一个n*m的matrix，元素为1、0
1代表小偷
定义(a,b)和(x,y)的Manhattan distance为|a - x| + |b - y|
一条路径为(0,0)到(n-1,m-1)
定义safeness factor为一条路径中任一元素到小偷的最短Manhattan distance
请找出一条有最大safeness factor的路径，并回传ｓsafeness factor
思路:
纪录每个1的位置，并用bfs去找出每个元素到1的最短距离，记录在dist矩阵
用maxheap去维护目前可以到达的元素
一开始把[0,0]丢到maxheap里
每次把离小偷最远的座标pop出来
接着把该座标4个方向的元素丢到maxheap里
并用ans纪录离小偷最短的距离
就这样一直到[n-1,m-1]后，回传ans
概念很早就想到了
不过一直超过时间
我这辈子就这样了，只能写一些垃圾code
golang code :
var dist [][]int
type h [][]int
func (this h) Len() int { return len(this) }
func (this h) Swap(i, j int) { this[i], this[j] = this[j], this[i] }
func (this h) Less(i, j int) bool { return dist[this[i][0]][this[i][1]] > dist
[this[j][0]][this[j][1]] }
func (this *h) Push(x interface{}) {
(*this) = append(*this, x.([]int))
}
func (this *h) Pop() interface{} {
tmp := (*this)[len(*this)-1]
(*this) = (*this)[:len(*this)-1]
return tmp
}
func maximumSafenessFactor(grid [][]int) int {
n,m:=len(grid),len(grid[0])
if grid[0][0]==1 || grid[n-1][m-1]==1{
return 0
}
queue:=make([][2]int,0)
dist=make([][]int,n)
visit:=make([][]bool,n)
arr:=[][]int{{1,0},{0,1},{-1,0},{0,-1}}
h:=h{{0,0}}
var ans int
for i:=0;i<n;i++{
dist[i]=make([]int,m)
visit[i]=make([]bool,m)
for j:=0;j<m;j++{
if grid[i][j]==1{
dist[i][j]=1
queue=append(queue,[2]int{i,j})
}
}
}
for len(queue)>0{
tmp:=queue[0]
queue=queue[1:]
for _,val:=range arr{
i:=tmp[0]+val[0]
j:=tmp[1]+val[1]
if i>-1 && j>-1 && i<n && j<m && dist[i][j]==0{
dist[i][j]=dist[tmp[0]][tmp[1]]+1
queue=append(queue,[2]int{i,j})
}
}
}
ans=dist[0][0]
visit[0][0]=true
for len(h)>0{
tmp:=heap.Pop(&h).([]int)
ans=min(ans,dist[tmp[0]][tmp[1]])
for _,val:=range arr{
i:=tmp[0]+val[0]
j:=tmp[1]+val[1]
if i==n-1 && j==m-1{
return min(ans,dist[i][j])-1
}
if i>-1 && j>-1 && i<n && j<m && !visit[i][j] {
heap.Push(&h,[]int{i,j})
visit[i][j]=true
}
}
}
return 0
}