seo站内优化和站外优化,网站的管理跟新维护有哪些,最流行网站开发工具,如何做输入密码进入网站文章目录1. 题目2. 解题2.1 multimap2.2 Lambda 表达式排序2.3 BFS搜索1. 题目
给出 R 行 C 列的矩阵#xff0c;其中的单元格的整数坐标为 (r, c)#xff0c;满足 0 r R 且 0 c C。
另外#xff0c;我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格…
文章目录1. 题目2. 解题2.1 multimap2.2 Lambda 表达式排序2.3 BFS搜索1. 题目
给出 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来源力扣LeetCode 链接https://leetcode-cn.com/problems/matrix-cells-in-distance-order 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 multimap
利用其有序性用距离作为keyvector 作为 value
class Solution {
public:vectorvectorint allCellsDistOrder(int R, int C, int r0, int c0) {vectorvectorint ans;multimapint,vectorint m;int i, j, k 0;for(i 0; i R; i){for(j 0; j C; j)m.emplace(pairint,vectorint (abs(i-r0)abs(j-c0),vectorint ({i,j})));}for(auto kv : m)ans.push_back(kv.second);//可以把多个vectorint一起push进去神奇return ans;}
};2.2 Lambda 表达式排序
class Solution {
public:vectorvectorint allCellsDistOrder(int R, int C, int r0, int c0) {vectorvectorint ans(R*C);int i, j, k 0;for(i 0; i R; i)for(j 0; j C; j)ans[k] {i,j};//[],里面的表示表示式所在区域的外部变量可见且是引用传递之前没写报错sort(ans.begin(), ans.end(), [](auto a, auto b){return abs(a[0]-r0)abs(a[1]-c0) abs(b[0]-r0)abs(b[1]-c0);});return ans;}
};2.3 BFS搜索
class Solution {vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};
public:vectorvectorint allCellsDistOrder(int R, int C, int r0, int c0) {vectorvectorint ans(R*C);bool visited[R][C];memset(visited, 0, sizeof visited);queuepairint,int q;pairint,int tp;q.push({r0,c0});visited[r0][c0] true;int x, y, k, i 0;while(!q.empty()){tp q.front();q.pop();ans[i] {tp.first, tp.second};for(k 0; k 4; k){x tp.first dir[k][0];y tp.second dir[k][1];if(x0 xR y0 yC !visited[x][y]){q.push({x,y});visited[x][y] true;}}}return ans;}
};
