题目描述
给出 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 <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C
Python
想法一：
一次到位，从(r0,c0)周围出发，按距离直接加入list中（然后i+j=n这种情况被自己蠢到了，不太会写，先放着，一会看别人的解析）
想法二：
遍历一遍整个矩阵，计算每个元素的距离，然后按照距离排序输出即可
这个地方踩了一个坑，用dict存储遍历结果时，一开始想以坐标对为key，最后输出按value排序的key即可，但dict的key不可以是list；因此，选择以距离为key，将同距离的坐标存为list，最后按距离大小拼接list
合并list：
a += b #方法一
a.extend(b) #方法二
a[0:0]=b #将b中元素插入到list a的开头
（add）合并dict：
dict(a, **b) # 方法一，返回合并后的dict
dict(a.items()+b.items()) #方法二，返回合并后的dict
c = {} #方法三
c.update(a)
c.update(b)
dict排序：
sorted(dic.items(), key = lambda item:item[0]) # 按key排序
sorted(dic.items(), key = lambda item:item[1]) # 按value排序
sorted(dic.items(), key = lambda item:item[1]["a"]) #多重嵌套排序，按照value对应的dict中的key对应的value排序
sorted(d.keys()) #按key排序只输出key，返回key的list
sorted(d.values()) #按value排序只输出value，返回value的list
解题代码
class Solution(object):
def allCellsDistOrder(self, R, C, r0, c0):
"""
:type R: int
:type C: int
:type r0: int
:type c0: int
:rtype: List[List[int]]
"""
max_num = R * C
num_dict = {}
for i in range(0,R):
for j in range(0,C):
distance = abs(i-r0)+abs(j-c0)
num_dict.setdefault(distance,[])
lists = num_dict[distance]
lists.append([i,j])
num_dict[distance]=lists
rst = []
for k_v in sorted(num_dict.items(),key=lambda item:item[0]):
rst += k_v[1]
return rst
别人的简洁写法(但其实两种方法都很暴力，不够美)
olution:
def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
return sorted(((i,j) for i in range(R) for j in range(C), key= lambda p: abs(p[0]-r0)+abs(p[1]-c0))
C++
还是一样的思路，二叉树的思路还不太理解，后面理解了再补充
class Solution {
public:
vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
if (R < 0 || C <0 || r0 < 0 || c0 < 0){
return vector<vector<int>> ();
}
unordered_map<int, vector<vector<int>>> dict;
for(int i = 0; i < R; ++i) {
for(int j = 0; j < C; ++j) {
int val = abs(i - r0) + abs(j - c0);
dict[val].push_back(vector<int>({i,j}));
}
}
vector<int> keys;
for (auto val: dict){
keys.push_back(val.first);
}
sort(keys.begin(),keys.end());
vector<vector<int>> res;
for (auto val: keys){
res.insert(res.end(),dict[val].begin(),dict[val].end());
}
return res;
}
};
