→ sustainer123: 這題我原本想說dfs 結果直接超時 放棄 05/15 19:12
推 devilkool: 只要是matrix的我都苦手 05/15 19:14
推 sustainer123: 個人覺得圖是最陰間題目 05/15 19:16
→ JIWP: 寫看看，白癡題目，不能只有我寫 05/15 19:16
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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.61.97.213 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715771464.A.92D.html