這題首先可以確定的點是，如果想要找到一條安全的路徑，那必須要先算出一個每個點的 Safety factor， 這裡的 Safety factor 定義是 Mahattan distance 與最小的盜賊的距離。
- 因此這裡一定要使用 Multi source BFS 來計算 Safety factor，這樣計算的時間複雜度是 O(n)*O(n) = O(n2)
- 最開始我是使用每次全部遍歷來計算 Safety factor，這樣的時間複雜度是 O(nt), t is the number of thiefs，速度差非常多
其實 Multi Source Breadth First Search 就跟 Tree 的逐層遍歷很像，確保每個原點都是以相同的速度擴散，所以一次只能擴散一層。
1 0 0 1 2 0 1 2 3
0 0 0 => 2 0 2 => 2 3 2
0 0 1 0 2 1 3 2 1
- 如果每次都只以 1 層的速度擴散，那麼就可以確保每個原點都是以相同的速度擴散找到 Safety factor
如果確定了 Multi source BFS 的 Safety factor，那麼就可以考慮用什麼算法來找到最安全的路徑，並且求出最大的 Safety factor
- Binary Search 的使用是基於這裡我們可以確定 Safety factor 的範圍
- 這樣就可以用一個 Left 跟 Right 來試圖夾出最小的 Safety factor
以這個 Safety factor map 來舉例:
2 1 0
3 2 1
4 3 2
Left = 0, Right = 4, Mid = 2
- 找尋是否有一條路徑可以通過 Safety factor >= 2
- True, Res = 2, Left = 3
- 找尋是否有一條路徑可以通過 Safety factor >= 3
- False, Right = 2
- Left < Right End Search, Return Res.
這種方式雖然還是要做多次的 BFS，但可以把搜尋次數下降到 Log(n)。
- Time Complexity O(n2log(n)).
- Multi Source BFS is O(n2)
- Binary Search from 0 to n2 is O(log(n))
Solution:
const (
intMax int = int(^uint(0) >> 1)
)
var (
directions = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
)
func maximumSafenessFactor(grid [][]int) int {
// Find all thiefs and initialization grid.
thiefs := [][]int{}
for i := range grid {
for j := range grid {
if grid[i][j] == 1 {
grid[i][j] = 0
thiefs = append(thiefs, []int{i, j})
} else{
grid[i][j] = -1
}
}
}
// Multi Source BFS to calculate each element safeness.
multiSourceBFS(&grid, thiefs)
maxSafe := 0
for i := range grid {
for j := range grid[i] {
maxSafe = max(maxSafe, grid[i][j])
}
}
res := 0
left, right := 0, maxSafe
for left <= right {
mid := left + (right - left) / 2
if bfs(grid, mid) {
res = mid
left = mid + 1
} else {
right = mid - 1
}
}
return res
}
func bfs(grid [][]int, mid int) bool {
n, m := len(grid), len(grid[0])
if grid[0][0] < mid || grid[n-1][n-1] < mid {
return false
}
visited := map[int]bool{ 0:true }
queue := []int{0}
for len(queue) > 0 {
// Decode index to [i, j], is to store it as x*n+y when storing.
i, j := queue[0]/n, queue[0]%n
queue = queue[1:]
if i == n-1 && j == n -1 {
return true
}
for _, d := range directions {
x, y := i+d[0], j+d[1]
if x < 0 || x >= n || y < 0 || y >= m {
continue
}
if visited[x*n+y] || grid[x][y] < mid {
continue
}
queue = append(queue, x*n+y)
visited[x*n+y] = true
}
}
return false
}
func multiSourceBFS(grid *[][]int, queue [][]int) {
n, m := len((*grid)), len((*grid)[0])
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
cur := queue[i]
i, j := cur[0], cur[1]
for _, d := range directions {
di, dj := i+d[0], j+d[1]
if di < 0 || di >= n || dj < 0 || dj >= m {
continue
}
if (*grid)[di][dj] != -1 {
continue
}
(*grid)[di][dj] = (*grid)[i][j] + 1
queue = append(queue, []int{di, dj})
}
}
queue = queue[size:]
}
}當然最直覺的方式是直接找出一條最大安全的路徑，並且可以從左上到達右下，這樣就需要用 Max Heap BFS 來進行，前面的部分都是一樣的， 但是在 Search 的部分就需要改變一下。
- BFS 通常是使用 Queue 來進行，但是也可以用 MaxHeap 來進行，這樣就可以確保每次都是取出最大的 Safety factor 來進行搜尋
以這個 Safety factor map 來舉例，在每次 Pop 出來的都是最大的 Safety factor cell，只要在這條路徑上找最小的 Safety factor 就可以了:
2 1 0
3 2 1
4 3 2
- Heap [2], Pop 2, Push 1, 3, Res = 2
- Heap [3, 1], Pop 3, Push 2, 4, Res = 2
- Heap [4, 2, 1], Pop 4, Push 3, Res = 2
- Heap [3, 2, 2, 1], Pop 3, Push 2, Res = 2
- Heap [2, 2, 1], Pop 2, Push 1, Res = 2
- Heap [2, 1, 1], Pop 2, To the end.
- Return 2
Solution:
import (
"container/heap"
)
const (
intMax int = int(^uint(0) >> 1)
)
var (
directions = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
)
func maximumSafenessFactor(grid [][]int) int {
// Find all thiefs and initialization grid.
thiefs := []int{}
n := len(grid)
for i := range grid {
for j := range grid {
if grid[i][j] == 1 {
grid[i][j] = 0
thiefs = append(thiefs, i*n+j)
} else{
grid[i][j] = -1
}
}
}
// Multi Source BFS to calculate each element safeness.
multiSourceBFS(&grid, thiefs)
maxSafe := 0
for i := range grid {
for j := range grid[i] {
maxSafe = max(maxSafe, grid[i][j])
}
}
return maxHeapBFS(grid)
}
// Multi source BFS to calculate each element safeness.
func multiSourceBFS(grid *[][]int, queue []int) {
n, m := len((*grid)), len((*grid)[0])
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
i, j := queue[i]/n, queue[i]%n
for _, d := range directions {
x, y := i+d[0], j+d[1]
if x < 0 || x >= n || y < 0 || y >= m {
continue
}
if (*grid)[x][y] != -1 {
continue
}
(*grid)[x][y] = (*grid)[i][j] + 1
queue = append(queue, x*n+y)
}
}
queue = queue[size:]
}
}
type Cell struct {
safeness int
index int
}
type CellMaxHeap []Cell
func (h CellMaxHeap) Len() int {
return len(h)
}
func (h CellMaxHeap) Less(i, j int) bool {
return h[i].safeness > h[j].safeness
}
func (h CellMaxHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *CellMaxHeap) Push(x interface{}) {
*h = append(*h, x.(Cell))
}
func (h *CellMaxHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
// Find a path from the grid start to the end.
func maxHeapBFS(grid [][]int) int {
n, m := len(grid), len(grid[0])
if grid[0][0] == 0 && grid[n-1][m-1] == 0 {
return 0
}
res := intMax
cells := &CellMaxHeap{}
heap.Init(cells)
heap.Push(cells, Cell{safeness: grid[0][0], index: 0})
visited := map[int]bool{ 0: true }
for cells.Len() > 0 {
cur := heap.Pop(cells).(Cell)
i, j := cur.index/n, cur.index%n
res = min(res, grid[i][j])
if i == n-1 && j == n-1 {
return res
}
for _, d := range directions {
x, y := i+d[0], j+d[1]
if x < 0 || x >= n || y < 0 || y >= m {
continue
}
if visited[x*n+y] {
continue
}
heap.Push(cells, Cell{safeness: grid[x][y], index: x*n+y})
visited[x*n+y] = true
}
}
return 0
}