題目描述 [ 距離順序排列矩陣單元格]
給出 R 行 C 列的矩陣，其中的單元格的整數(shù)坐標(biāo)為 (r, c)蛔琅，滿足 0 <= r < R 且 0 <= c < C仪糖。
另外鹤竭，我們?cè)谠摼仃囍薪o出了一個(gè)坐標(biāo)為 (r0, c0) 的單元格挂脑。
返回矩陣中的所有單元格的坐標(biāo)藕漱，并按到 (r0, c0) 的距離從最小到最大的順序排欲侮，其中，兩單元格(r1, c1) 和 (r2, c2) 之間的距離是曼哈頓距離肋联，|r1 - r2| + |c1 - c2|威蕉。（你可以按任何滿足此條件的順序返回答案。）
示例
輸入：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]] 也會(huì)被視作正確答案橄仍。
解題思路一
- 廣度優(yōu)先搜索
- 要把xy坐標(biāo)都存下來韧涨，所以略微復(fù)雜了點(diǎn)把
代碼
class Solution {
public:
void push(int i, int j, queue<pair<int, int> > &queue1, int R, int C){
if(i<0||i>R-1||j<0||j>C-1) return;
else{
queue1.push(make_pair(i, j));
}
}
vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
vector<vector<int> > res;
queue<pair<int, int> > queue1;
set<pair<int, int> > hashset;
if(R==0 || C==0) return res;
queue1.push(make_pair(r0, c0));
// hashset.insert(make_pair(r0, c0));
while(!queue1.empty()){
auto temp = queue1.front();
queue1.pop();
if(hashset.count(temp)==0){
hashset.insert(temp);
vector<int> ans;
ans.push_back(temp.first);
ans.push_back(temp.second);
res.push_back(ans);
push(temp.first-1, temp.second, queue1, R, C);
push(temp.first+1, temp.second, queue1, R, C);
push(temp.first, temp.second-1, queue1, R, C);
push(temp.first, temp.second+1, queue1, R, C);
}
}
return res;
}
};
解題思路二
- 把矩陣中的點(diǎn)到目標(biāo)點(diǎn)的距離按照距離進(jìn)行排序輸出即可
- 大概是腦殘所以才會(huì)想到上面那么復(fù)雜的解法把
代碼
class Solution {
public:
vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
vector<vector<int>> res(R*C,vector<int>(3));
int num=0;
for(int i=0;i<C;i++)
{
for(int j=0;j<R;j++)
{
res[num][0]=j;
res[num][1]=i;
res[num][2]=abs(r0-j)+abs(c0-i);
num++;
}
}
sort(res.begin(),res.end(),ismax);//排序
for(int i=0;i<num;i++)//將曼哈頓距離刪除
{
res[i].pop_back();
}
return res;
}
static bool ismax(vector<int> &a,vector<int> &b)
{
return a[2]<b[2];
}
};
