1030. 距離順序排列矩陣單元格

題目來源：力扣（LeetCode）https://leetcode-cn.com/problems/matrix-cells-in-distance-order/

題目

給出 R 行 C 列的矩陣，其中的單元格的整數坐標為 (r, c)，滿足 0 <= r < R 且 0 <= c < C，

另外，我們在該矩陣中給出了一個坐標為 (r0, c0) 的單元格，

回傳矩陣中的所有單元格的坐標，并按到 (r0, c0) 的距離從最小到最大的順序排，其中，兩單元格(r1, c1) 和 (r2, c2) 之間的距離是曼哈頓距離，|r1 - r2| + |c1 - c2|，（你可以按任何滿足此條件的順序回傳答案，）

示例 1：

輸入：R = 1, C = 2, r0 = 0, c0 = 0
輸出：[[0,0],[0,1]]
解釋：從 (r0, c0) 到其他單元格的距離為：[0,1]

示例 2：

輸入：R = 2, C = 2, r0 = 0, c0 = 1
輸出：[[0,1],[0,0],[1,1],[1,0]]
解釋：從 (r0, c0) 到其他單元格的距離為：[0,1,1,2]
[[0,1],[1,1],[0,0],[1,0]] 也會被視作正確答案，

示例 3：

輸入：R = 2, C = 3, r0 = 1, c0 = 2
輸出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
解釋：從 (r0, c0) 到其他單元格的距離為：[0,1,1,2,2,3]
其他滿足題目要求的答案也會被視為正確，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]，

提示：

1. 1 <= R <= 100
2. 1 <= C <= 100
3. 0 <= r0 < R
4. 0 <= c0 < C

解題思路

思路：直接排序、桶排序、BFS

先審題，本題題意弄清楚后，就會有直觀的解法，

首先題目給出的 R R R 行 C C C 列的矩陣，其中：

• 矩陣中的單元格坐標為 ( r , c ) (r, c) (r,c)，這里 0 ≤ r < R 0 \leq r < R 0≤r<R 且 0 ≤ c < C 0 \leq c < C 0≤c<C；

題目中還給出一個坐標為 ( r 0 , c 0 ) (r0, c0) (r0,c0) 的單元格，（這個單元格在給定的矩陣內，其實就是從矩陣中挑一個坐標）

現在題目要求的是回傳矩陣所有單元格坐標，要求單元格坐標到 ( r 0 , c 0 ) (r0, c0) (r0,c0) 的距離大小順序排列，其中這里的距離指的是曼哈頓距離，

在這里，假設存在兩單元格 ( r 1 , c 1 ) (r1, c1) (r1,c1) 和 ( r 2 , c 2 ) (r2, c2) (r2,c2)，那么兩者之間的曼哈頓距離就是：
d ( i , j ) = ∣ r 1 ? r 2 ∣ + ∣ c 1 ? c 2 ∣ d(i, j) = |r1 - r2| + |c1 - c2| d(i,j)=∣r1?r2∣+∣c1?c2∣

直接排序

那么，這里其實就是排序的問題，只不過排序規則是：根據點到點之間的曼哈頓距離大小進行排序，

這里，先說下直接排序的方法：

• 先將矩陣中所有的單元格坐標都存盤在串列中；
• 然后進行排序，這里的排序規則則改成按照所有單元格坐標到給定的 ( r 0 , c 0 ) (r0, c0) (r0,c0) 單元格的曼哈頓距離大小升序排序，

具體的代碼實作如下，

class Solution:
    def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
        # 先將所有的坐標都放到串列中
        res = [(r, c) for r in range(R) for c in range(C)]
        # 改變排序的規則，根據曼哈頓距離的大小排序
        res.sort(key=lambda x: abs(x[0] - r0) + abs(x[1] - c0))
        return res

桶排序

上面的直接排序的思路，首先需要先將所有的坐標點都放到串列中，然后再進行排序，時間復雜度較高，

這里我們可以使用桶排序，根據曼哈頓距離，將坐標放到對應的桶中，具體的思路如下：

• 首先先求得坐標之間的最大曼哈頓距離；（見示例，坐標之間的距離串列中，可能存在相同的距離，但會有一個最大的距離，）
• 根據求得的最大曼哈頓距離，確定桶的數量，根據曼哈頓距離分桶，相同的放到同個桶中；
• 最后，將桶中的坐標，根據距離大小添加到結果串列中，

具體的代碼實作如下，

class Solution:
    def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
        def get_d(r, c, r0, c0):
            """求曼哈頓距離
            """
            return abs(r-r0) + abs(c-c0)
        
        # 確定曼哈頓距離的最大值，進而確定桶數量
        max_d = max(r0, R - 1 - r0) + max(c0, C - 1 - c0)
        # 初始化桶，遍歷將坐標放入根據曼哈頓距離放到對應的桶中
        bucket = {}
        for r in range(R):
            for c in range(C):
                d = get_d(r, c, r0, c0)
                if d not in bucket:
                    bucket[d] = []
                bucket[d].append([r, c])
        
        # 將桶中元素添加到結果串列中
        res = []
        for i in range(max_d+1):
            res.extend(bucket[i])
        
        return res

BFS

這里，我們也可以用 BFS 的思路來實作，具體的思路如下：

• 以給定的坐標 ( r 0 , c 0 ) (r0, c0) (r0,c0) 作為起始點，出隊，開始往四周的坐標點進行擴散；
• 擴散時，需要注意邊界問題，以及是否被擴散訪問過；
• 這里入佇列，是根據曼哈頓距離從小到大進行入隊，

具體的代碼實作如下，

class Solution:
    def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
        # 四個方位
        dire = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        
        # 標記是否已經被擴散訪問過
        signed = [[False] * C for _ in range(R)]
        
        queue = collections.deque()
        # 添加起始點
        queue.append([r0, c0])
        # 標記已擴散
        signed[r0][c0] = True

        res = []
        while queue:
            # 出列，準備擴散
            cur =  queue.popleft()
            res.append(cur)

            r, c = cur
            # 開始往四周擴散
            for _ in range(4):
                for i, j in dire:
                    nr = r + i
                    nc = c + j
                    # 注意邊界，以及是否被擴散訪問過
                    if 0 <= nr < R and 0 <= nc < C and not signed[nr][nc]:
                        queue.append([nr, nc])
                        signed[nr][nc] = True
            
        return res

歡迎關注

公眾號 【書所集錄】

如有錯誤，煩請指出，歡迎指點交流，