[LeetCode] 1030. Matrix Cells in Distance Order

[grandyang]

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

这道题给了一个R行C列的矩阵，又给了一个起始点 (r0, c0)，让按照离起始点的曼哈顿距离从小到大排序坐标点。博主最先想到的方法就是从起始点开始进行广度优先遍历 Breadth-First Search，这样保证了离起始点的距离是从小到大的，在遍历的过程中将坐标加入结果 res 即可，写法就是最普通的 BFS 遍历，没有太多需要注意的地方，参见代码如下：

解法一：

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[0] + dir[0], y = t[1] + dir[1];
                if (x < 0 || x >= R || y < 0 || y >= C || visited.count({x, y})) continue;
                visited.insert({x, y});
                q.push({x, y});
            }
        }
        return res;
    }
};

其实我们并不用写个 BFS 那么麻烦，直接自定义一个 comparator 给 res 数组重新排序即可，自定义的 comparator 要把 (r0, c0) 当参数传进去，因为要求和其的曼哈顿距离，参见代码如下：

解法二：

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[0] - r0) + abs(a[1] - c0) < abs(b[0] - r0) + abs(b[1] - c0);
        });
        return res;
    }
};

Github 同步地址:

#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 题目讲解汇总(持续更新中...)