Leetcode 1030. Matrix Cells in Distance Order

以你之姓@ 2022-09-09 00:11 1阅读 0赞

文章作者：Tyan  
博客：[noahsnail.com][] | [CSDN][] | [简书][Link 1]

## 1. Description ##

![Matrix Cells in Distance Order][]

## 2. Solution ##

\*\*解析：\*\*Version 1，直接根据距离进行排序。Version 使用广度优先搜索。

*  Version 1

class Solution:
        def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:
            coordinates = [[i, j] for i in range(rows) for j in range(cols)]
            coordinates.sort(key=lambda x: abs(x[0] - rCenter) + abs(x[1] - cCenter))
            return coordinates

*  Version 2

class Solution:
        def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:
            matrix = [[0] * cols for i in range(rows)]
            queue = collections.deque()
            queue.append((rCenter, cCenter))
            matrix[rCenter][cCenter] = 1
            coordinates = []
            while queue:
                x, y = queue.popleft()
                coordinates.append([x, y])
                matrix[x][y] = 1
                if x > 0 and matrix[x-1][y] == 0:
                    matrix[x-1][y] = 1
                    queue.append((x-1, y))             
                if x < rows - 1 and matrix[x+1][y] == 0:
                    matrix[x+1][y] = 1
                    queue.append((x+1, y))   
                if y > 0 and matrix[x][y-1] == 0:
                    matrix[x][y-1] = 1
                    queue.append((x, y-1))             
                if y < cols - 1 and matrix[x][y+1] == 0:
                    matrix[x][y+1] = 1
                    queue.append((x, y+1))   
            return coordinates

## Reference ##

1.  [https://leetcode.com/problems/matrix-cells-in-distance-order/][https_leetcode.com_problems_matrix-cells-in-distance-order]

[noahsnail.com]: http://noahsnail.com
[CSDN]: http://blog.csdn.net/quincuntial
[Link 1]: http://www.jianshu.com/users/7731e83f3a4e/latest_articles
[Matrix Cells in Distance Order]: /images/20220829/b1711d02964346abb00911147f73844a.png
[https_leetcode.com_problems_matrix-cells-in-distance-order]: https://leetcode.com/problems/matrix-cells-in-distance-order/