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

Andrew Schultz on Unsplash

題目敘述

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

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

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

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

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

原本的英文題目敘述

測試範例

Example 1:

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:

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:

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 )

需要一個２Ｄ掃描，掃描每個格子點恰好掃描一次，耗費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