# 1030. Matrix Cells in Distance Order

We are given a matrix with `R` rows and `C` columns has cells with integer coordinates `(r, c)`, where `0 <= r < R` and `0 <= c < C`.

Additionally, we are given a cell in that matrix with coordinates `(r0, c0)`.

Return the coordinates of all cells in the matrix, sorted by their distance from `(r0, c0)` from smallest distance to largest distance.  Here, the distance between two cells `(r1, c1)` and `(r2, c2)` is the Manhattan distance, `|r1 - r2| + |c1 - c2|`.  (You may return the answer in any order that satisfies this condition.)

Example 1:

``````Input: R = 1, C = 2, r0 = 0, c0 = 0
Output: [[0,0],[0,1]]
Explanation: The distances from (r0, c0) to other cells are: [0,1]
``````

Example 2:

``````Input: R = 2, C = 2, r0 = 0, c0 = 1
Output: [[0,1],[0,0],[1,1],[1,0]] Explanation: The distances from (r0, c0) to other cells are: [0,1,1,2]
The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.
``````

Example 3:

``````Input: R = 2, C = 3, r0 = 1, c0 = 2
Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
Explanation: The distances from (r0, c0) to other cells are: [0,1,1,2,2,3]
There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].
``````

Note:

1. `1 <= R <= 100`
2. `1 <= C <= 100`
3. `0 <= r0 < R`
4. `0 <= c0 < C`

``````class Solution {
public:
vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
vector<vector<int>> res;
set<vector<int>> visited;
vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
queue<vector<int>> q;
q.push({r0, c0});
visited.insert({r0, c0});
while (!q.empty()) {
auto t = q.front(); q.pop();
res.push_back(t);
for (auto dir : dirs) {
int x = t + dir, y = t + dir;
if (x < 0 || x >= R || y < 0 || y >= C || visited.count({x, y})) continue;
visited.insert({x, y});
q.push({x, y});
}
}
return res;
}
};
``````

``````class Solution {
public:
vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
vector<vector<int>> res;
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
res.push_back({i, j});
}
}
sort(res.begin(), res.end(), [r0, c0](vector<int>& a, vector<int>& b) {
return abs(a - r0) + abs(a - c0) < abs(b - r0) + abs(b - c0);
});
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1030

https://leetcode.com/problems/matrix-cells-in-distance-order/

https://leetcode.com/problems/matrix-cells-in-distance-order/discuss/278843/O(N)-Java-BFS

https://leetcode.com/problems/matrix-cells-in-distance-order/discuss/278807/c%2B%2B-sorting-min-heap-solutions

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏 ×

Help us with donation  