本文共 2863 字，大约阅读时间需要 9 分钟。

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 = 0Output: [[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 = 1Output: [[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 = 2Output: [[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 <= R <= 100
• 1 <= C <= 100
• 0 <= r0 < R
• 0 <= c0 < C

题意：给出 R 行 C 列的矩阵，其中单元格的整数坐标为 (r, c)，满足 0 <= r < R 且 0 <= c < C。另外，在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。返回矩阵中的所有单元格的坐标序列，并按到 (r0, c0) 的曼哈顿距离从最小到最大的顺序排。

解法1 排序

先生成矩阵坐标序列，然后按照要求排序：

class Solution {
   public:    vector
   
    
     > allCellsDistOrder(int R, int C, int r0, int c0) {
           vector
     
      
       > 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(), [&](const vector
       
         &a, const vector
        
          &b) { return abs(a[0] - r0) + abs(a[1] - c0) < abs(b[0] - r0) + abs(b[1] - c0); }); return res; }};
        
       
      
     
    
   

提交结果如下：

执行用时：104 ms, 在所有 C++ 提交中击败了55.53% 的用户内存消耗：16.7 MB, 在所有 C++ 提交中击败了54.21% 的用户

解法2 BFS

按照二叉树的层序遍历，从中心点逐步向上下左右扩散：

class Solution {
   public:    vector
   
    
     > allCellsDistOrder(int R, int C, int r0, int c0) {
           vector
     
      
       > ans;        int moves[][2] = {
   0, -1, -1, 0, 0, 1, 1, 0};        queue
       
        
         > q; vis[r0][c0] = true; q.push({ r0, c0}); //将中心点加入队列 ans.push_back({ r0, c0}); vector
         
          
           > vis(R, vector
           
            (C)); //标记矩阵 while (!q.empty()) { int size = q.size(); for (int i = 0; i < size; ++i) { vector
            
              t = q.front(); q.pop(); for (int i = 0; i < 4; ++i) { int tx = t[0] + moves[i][0], ty = t[1] + moves[i][1]; if (tx >= 0 && tx < R && ty >= 0 && ty < C && !vis[tx][ty]) { vis[tx][ty] = true; q.push({ tx, ty}); ans.push_back({ tx, ty}); } } } } return ans; }};
            
           
          
         
        
       
      
     
    
   

提交后效率如下：

执行用时：132 ms, 在所有 C++ 提交中击败了31.70% 的用户内存消耗：24.3 MB, 在所有 C++ 提交中击败了27.42% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/109736852 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！