題目描述
給出 R 行 C 列的矩陣疗隶，其中的單元格的整數(shù)坐標(biāo)為 (r, c)搏讶，滿足 0 <= r < R 且 0 <= c < C改艇。
另外兰粉，我們在該矩陣中給出了一個坐標(biāo)為 (r0, c0) 的單元格焊唬。
返回矩陣中的所有單元格的坐標(biāo)艇搀，并按到 (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)周圍出發(fā)，按距離直接加入list中（然后i+j=n這種情況被自己蠢到了空幻，不太會寫烁峭，先放著，一會看別人的解析）
想法二：
遍歷一遍整個矩陣秕铛，計算每個元素的距離约郁，然后按照距離排序輸出即可
這個地方踩了一個坑，用dict存儲遍歷結(jié)果時但两，一開始想以坐標(biāo)對為key评抚，最后輸出按value排序的key即可谜酒，但dict的key不可以是list进鸠；因此各拷，選擇以距離為key，將同距離的坐標(biāo)存為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對應(yīng)的dict中的key對應(yīng)的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;
}
};
