“This is the 11th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

The question to describe

The matrix of row R and column C is given, where the integer coordinates of the cells are (R, C), satisfying 0 <= R < R and 0 <= C < C.

In addition, we give a cell with coordinates (R0, c0) in the matrix.

Returns the coordinates of all the cells in the matrix, and press (r0, c0) distance from the smallest to the largest order, among them, the two cell (r1, c1) and (r2, c2), Manhattan distance is the distance between | r1 and r2 + | c1 and c2 | |. (You can return the answers in any order that satisfies this condition.)

Example 1:

Input: R = 1, C = 2, R0 = 0, c0 = 0 Output: [[0,0],[0,1]

Example 2:

Input: R = 2, C = 2, r0 = 0, c0 = 1 output: [[0, 1], [0, 0], [1, 1], [1, 0]] : from (r0, c0) to the other cells: [0,1, 2] [[0,1],[1,1],[0,0],[1,0]] will also be considered the correct answer.

Solution 1: sort+ hash

We can first calculate the distance between each cell and [r0, c0], and then use the distance as the key and the value of the cell as the value to create a hash table, i.e. hash[distance].push([r, c]). I’m going to hash it out, flatten the two-dimensional array

var allCellsDistOrder = function(R, C, r0, c0) {
    const res = [];
    for(let i = 0; i < R; i++) {
        for(let j = 0; j < C; j++) {
            res.push([i,j]);
        }
    }
    res.sort((a,b) = > (Math.abs(a[0] - r0) + Math.abs(a[1] - c0) - Math.abs(b[0] - r0) - Math.abs(b[1] - c0)));
    return res;
};

Copy the code
Solution 2: BFS

Analysis: We create a two-dimensional array of rows R and columns C, with coordinates I and j, and then iterate breadth-first

function allCellsDistOrder(R, C, r0, c0) {
      let matrix= new Array(R*C).fill(0).map(v= >new Array(2).fill(0));// All the points in the matrix
      let visited= new Array(R).fill(0).map(v= >new Array(C).fill(false));/ / memory
      const direction =[[-1.0], [1.0], [0, -1], [0.1]]/ / direction

      let index = 1;    / / matrix index
      let level = 0;  // Explore around the matrix for each point
      matrix[0] = [r0, c0];// The smallest point is itself
      visited[r0][c0] = true;

      // Iterate over all the points
      while(index < R * C){  

          for(let i=0; i<4; i++){
              let ri = matrix[level][0] + direction[i][0];
              let ci = matrix[level][1] + direction[i][1];

              if(ri >= 0 && ri < R && ci >= 0 && ci < C){  
                  if(! visited[ri][ci] && index < R * C){ matrix[index] =[ri,ci]; visited[ri][ci] =true;
                      index++;// Move on to the next one
                  }
              }
          }

          level++; // Explore the next point
      }
      return matrix;
}
Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤