【Leetcode】1030. Matrix Cells in Distance Order

题目地址：

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

有一个$m\times n$的矩阵，再给定其中一个位置$(r,c)$，将矩阵里所有的坐标按和$(r,c)$的曼哈顿距离从近到远排序，然后将这$m\times n$个位置返回。

直接模拟。曼哈顿距离离$(r,c)$相等的点构成一个菱形，暴力求出所有点即可。代码如下：

class Solution {
 public:
  vector<vector<int>> allCellsDistOrder(int m, int n, int r, int c) {
    vector<vector<int>> res = {{r, c}};
    int dx[] = {1, 1, -1, -1};
    int dy[] = {1, -1, -1, 1};
    for (int d = 1; res.size() < m * n; d++) {
      int x = r - d, y = c;
      for (int i = 0; i < 4; i++)
        for (int j = 0; j < d; j++) {
          if (0 <= x && x < m && 0 <= y && y < n) res.push_back({x, y});
          x += dx[i], y += dy[i];
        }
    }

    return res;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度$O(m^2+n^2)$，空间$O(1)$。