平安歸途 最安全的一條路 (圖論應用) Leetcode #2812

閱讀時間約 11 分鐘

題目敘述

題目給定一個二元矩陣,用1來代表小偷所在的位置,0代表沒有小偷。

每個格子點的安全分數為該點距離小偷的曼哈頓距離(Manhanttan distance)

一條路徑的安全分數是路徑上所有安全分數的最小值

移動的時候可以往上、下、左、右走一格。

請問從左上角走到右下角的最安全路徑的安全分數是多少


原本的英文題目敘述


測試範例

Example 1:

raw-image


Input: grid = [[1,0,0],[0,0,0],[0,0,1]]
Output: 0
Explanation: All paths from (0, 0) to (n - 1, n - 1) go through the thieves in cells (0, 0) and (n - 1, n - 1).


Example 2:

raw-image


Input: grid = [[0,0,1],[0,0,0],[0,0,0]]
Output: 2
Explanation: The path depicted in the picture above has a safeness factor of 2 since:
- The closest cell of the path to the thief at cell (0, 2) is cell (0, 0). The distance between them is | 0 - 0 | + | 0 - 2 | = 2.
It can be shown that there are no other paths with a higher safeness factor.


Example 3:

raw-image
Input: grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
Output: 2
Explanation: The path depicted in the picture above has a safeness factor of 2 since:
- The closest cell of the path to the thief at cell (0, 3) is cell (1, 2). The distance between them is | 0 - 1 | + | 3 - 2 | = 2.
- The closest cell of the path to the thief at cell (3, 0) is cell (3, 2). The distance between them is | 3 - 3 | + | 0 - 2 | = 2.
It can be shown that there are no other paths with a higher safeness factor.
 

約束條件

Constraints:

  • 1 <= grid.length == n <= 400

輸入陣列的邊長n介於1~400之間。

  • grid[i].length == n

輸入陣列的邊長以n代表

  • grid[i][j] is either 0 or 1.

每個陣列元素一定是零(沒有小偷) 或 一(有小偷)。

  • There is at least one thief in the grid.

地圖中至少有一位小偷。


演算法 Dijkstra找最安全路徑


怎麼計算每個格子點的安全分數?

根據定義,
根據每個格子點和小偷的曼哈頓距離來計算。
( delta x + delta y = 水平距離差值 + 垂直距離差值)


怎麼找最安全路徑?

起點設為左上角,終點設為右下角。

使用Dijkstra algorithm,
每回合都從當前四聯通N4的鄰居取出安全分數最高的格子點,作為探索前進的方向


程式碼 Dijkstra找最安全路徑

class Solution:
def maximumSafenessFactor(self, grid: List[List[int]]) -> int:

# Heigh as well as width of board
h, w = len(grid), len(grid[0])

## Simple case:
# Either source or destination has thief.
# Not safe always => Safety score = 0
if grid[0][0] == 1 or grid[h-1][w-1] == 1:
return 0

## Dictionary
# key: coordination
# value: corresponding safeness score
safeness = defaultdict(lambda :-1)

bfs_queue = deque([])

## Step 1:
# Collect thief information
for r in range(h):
for c in range(w):
if grid[r][c] == 1:
safeness[r,c] = 0
bfs_queue.append((0, r, c))

## Step 2:
# Propagate safeness value based on Manhanttan distance to thief
N4_vector = [(-1,0),(1,0),(0,-1),(0,1)]
while bfs_queue:
dis, r, c = bfs_queue.popleft()

for dr, dc in N4_vector:
nr, nc = r + dr, c + dc

if 0 <= nr < h and 0 <= nc < w and safeness[nr,nc] == -1:
safeness[nr,nc] = dis + 1
bfs_queue.append((dis + 1, nr, nc))


## Step 3:
# Try to find safest path from source to destination, flip to negative to fit in python's minHeap in order to select safest path
safety_queue = [(-safeness[0,0], 0, 0)]

# Initialize to source point
seen = set([(0,0)])

# Dijkstra: always pick safer path first
while safety_queue:
safety, r, c = heappop(safety_queue)

# Flip back to positive value
safety *= -1

# Base case: we've reached destination
if (r, c) == (h-1, w-1):
return safety

## General cases:
# Check neighbor in N4, and update safety value, push back into priority queue on safety
for dr, dc in N4_vector:
nr, nc = r + dr, c + dc

# Neighbor is on the board, and it has not been seen yet.
if 0 <= nr < h and 0 <= nc < w and (nr, nc) not in seen:

# Update path safety = min{ safety value on the path so far}
path_safety = min(safety, safeness[nr,nc] )

# Push back into priorty queue
heappush(safety_queue, (-path_safety, nr, nc))

# Mark this neighbor as seen
seen.add((nr, nc))


# If no path to destination, return -1 as no solution
return -1

複雜度分析

時間複雜度: O(n^2 log n^2 )

需要一個2D掃描,掃描每個格子點恰好掃描一次,耗費O(n^2)時間。

接著使用Dijkstra algorithm + heap挑選最安全路徑,至多有O(n^2)個格子點,調整heap時,至多花費O(log n^2)的時間。


總共時間成本為O(n^2 + n^2 log n^2 ) = O( n^2 log n^2)


空間複雜度: O(n^2)

探索深度最深為O(n^2),最多就是將近探索整張圖,也就是queue的最大成本。


關鍵知識點

曼哈頓距離
= Manhantann distance
= 兩點之間的水平距離差距 + 垂直距離差距 = delta x + delta y


當遇到最短路徑最安全路徑最高分數路徑...等場景時,
聯想到圖論中的Dijkstra algorithm + priority queue

具體的優先權策略就根據題意進行計算即可
在本題中,最安全的路徑就是安全分數最高的路徑。


Reference

[1] Find the Safest Path in a Grid - LeetCode

46會員
294內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!