给出 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 <= R <= 1001 <= C <= 1000 <= r0 < R0 <= c0 < C
**难度**: Easy
**标签**: 排序、
# -*- coding: utf-8 -*-
# @Author : LG
"""
执行用时：196 ms
内存消耗：15.6 MB
解题思路：
将所有的点存在一个列表里。
对列表按距离进行排序。
最简洁，但也最慢。
"""
class Solution:
def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
lists = [[r, c] for r in range(R) for c in range(C)]
lists = sorted(lists, key=lambda p: abs(p[0]-r0)+abs(p[1]-c0))
return lists
"""
执行用时：180 ms, 在所有 Python3 提交中击败了72.17% 的用户
内存消耗：15.5 MB, 在所有 Python3 提交中击败了100.00% 的用户
解题思路：
循环计算各点与原点距离，存入一个列表中，将同距离点都存在一个列表中，列表第一个元素中存储距离为1的点，第二个元素中存储距离为2的点。
遍历列表，获取点。
"""
class Solution:
def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int):
dists = [[] for _ in range(R+C)]
for r in range(abs(R)):
for c in range(abs(C)):
dists[abs(r-r0)+abs(c-c0)].append([r, c])
result = []
for dist in dists:
if dist !=[]:
result.extend(dist)
return result
"""
执行用时：172 ms
内存消耗：15.3 MB
解题思路：
思路与2相同，但将列表换成字段。
"""
class Solution:
def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int):
dists = {}
for r in range(abs(R)):
for c in range(abs(C)):
dist = abs(r-r0)+abs(c-c0)
if dist not in dists.keys():
dists[dist] = []
dists[dist].append([r, c])
result = []
dists_keys = sorted(dists.keys())
for dist in dists_keys:
result.extend(dists[dist])
return result