距离顺序排列矩阵单元格

难度: Easy

给定四个整数 rows , cols , rCenter 和 cCenter 。有一个 rows x cols 的矩阵，你在单元格上的坐标是 (rCenter, cCenter) 。

返回矩阵中的所有单元格的坐标，并按与 (rCenter, cCenter) 的距离从最小到最大的顺序排。你可以按任何满足此条件的顺序返回答案。

单元格(r1, c1) 和 (r2, c2) 之间的距离为|r1 - r2| + |c1 - c2|。

示例 1：

输入：rows = 1, cols = 2, rCenter = 0, cCenter = 0
输出：[[0,0],[0,1]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1]

示例 2：

输入：rows = 2, cols = 2, rCenter = 0, cCenter = 1
输出：[[0,1],[0,0],[1,1],[1,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]
[[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。

示例 3：

输入：rows = 2, cols = 3, rCenter = 1, cCenter = 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 <= rows, cols <= 100
0 <= rCenter < rows
0 <= cCenter < cols

Submission

运行时间: 35 ms

内存: 17.5 MB

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

Explain

此题解采用了直接生成和排序的方法。首先，使用列表推导式生成一个包含所有单元格坐标的列表。接着，使用排序函数对这些坐标按照它们到给定中心点 (rCenter, cCenter) 的曼哈顿距离进行排序。曼哈顿距离通过计算两点在行和列上的绝对差值之和来获得。排序后，列表中的单元格坐标就是按照从中心点出发的距离从小到大排序的。

时间复杂度: O((rows * cols) * log(rows * cols))

空间复杂度: O(rows * cols)

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:
        # 创建一个列表，包含矩阵中所有单元格的坐标
        ret = [(i, j) for i in range(rows) for j in range(cols)]
        # 对坐标列表按照每个点到中心点 (rCenter, cCenter) 的曼哈顿距离进行排序
        ret.sort(key=lambda x: abs(x[0] - rCenter) + abs(x[1] - cCenter))
        # 返回排序后的坐标列表
        return ret

Explore

列表推导式通过嵌套循环，对行使用 `for i in range(rows)` 和对列使用 `for j in range(cols)` 进行遍历。这种方式确保了从行的第0行到第rows-1行，从列的第0列到第cols-1列的每一个单元格坐标都被遍历一次。因为range函数生成从起始值到终止值（不包括终止值）的整数序列，所以这种遍历方式覆盖了矩阵中的所有单元格，没有遗漏。

排序函数使用曼哈顿距离作为排序的关键字，通过 `lambda x: abs(x[0] - rCenter) + abs(x[1] - cCenter)` 计算每个坐标到中心点的距离。Python 的排序函数是稳定的，这意味着如果有两个元素具有相同的键值（即曼哈顿距离相同），它们在排序后的列表中的相对位置会保持和排序前一致。因此，即使存在多个坐标具有相同的曼哈顿距离，它们的排序顺序是由它们在原始列表中的顺序决定的，从而保证了排序的稳定性。

在这个问题中，使用曼哈顿距离因为它更适合于网格布局的矩阵，其中移动只能沿着行和列进行。曼哈顿距离是一个更自然的选择，因为它直接反映了在网格内从一点到另一点的最少步骤数。若使用欧几里得距离，虽然它在几何上表示两点之间的直线距离，但在只能沿网格线移动的情况下不是一个实际的移动距离。在排序中使用欧几里得距离可能会导致与实际步骤数不同的排序结果，尤其是在多个点距离相近时。

确实存在不需要进行完整排序的更优方法。一种方法是使用广度优先搜索（BFS），从中心点开始进行层序遍历，逐层扩展到所有的单元格。这种方法利用了队列结构来依次访问和添加每个单元格的四个方向邻居（如果它们在矩阵内）。这样可以按照从中心点到其他点的实际距离增加的顺序访问每个单元格，从而避免了整体排序的需要。这种方法的时间复杂度通常比直接排序更优，尤其是在矩阵较大时更为明显。