LeetCode – 1030. Arrange matrix cells in distance order

The title

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]Copy the code

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.Copy the code

Example 3:

Input: R = 2, C = 3, r0 = 1, 2 c0 = output: [[1, 2], [0, 2], [1, 1], [0, 1], [1, 0] to [0, 0]] : from (r0, c0) to the other cells: ,1,1,2,2,3 [0] other answers that could satisfy the requirement of subject will be considered right, such as [[1, 2], [1, 1], [0, 2], [1, 0], [0, 1], [0, 0]].Copy the code

Note:

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

Their thinking

1. Sort directly

  1. Store all the points in the matrix
  2. Sort them directly by the Hamandon distance
/ * * *@param {number} R
 * @param {number} C
 * @param {number} r0
 * @param {number} c0
 * @return {number[][]}* /
var allCellsDistOrder = function(R, C, r0, c0) {
    // Store all the points in the matrix
    const res = []
    for (let i = 0; i < R; i++) {
        for (let j = 0; j < C; j++) {
            res.push([i, j])
        }
    }
    // Get the Manhattan distance
    function getD(x1, y1) {
        return Math.abs(x1 - r0) + Math.abs(y1 - c0)
    }
    // Sort and return
    return res.sort((a, b) = > getD(a[0], a[1]) - getD(b[0], b[1))};Copy the code

2. Bucket sort

  1. Buckets are sorted by Manhattan distance when enumerating all points
  2. Use flat
/ * * *@param {number} R
 * @param {number} C
 * @param {number} r0
 * @param {number} c0
 * @return {number[][]}* /
var allCellsDistOrder = function(R, C, r0, c0) {
    // The storage is sorted according to the Manhattan distance
    const res = []
    for (let i = 0; i < R; i++) {
        for (let j = 0; j < C; j++) {
            // Get the Manhattan distance of the current point
            const distances = getD(i, j)
            // The bucket already exists
            if (res[distances]) res[distances].push([i, j])
            // Create a bucket if the bucket does not exist
            else res[distances] = [[i, j]]
        }
    }
    // Get the Manhattan distance
    function getD(x1, y1) {
        return Math.abs(x1 - r0) + Math.abs(y1 - c0)
    }
    // Sort and return
    return res.flat()
};
Copy the code

3. BFS/geometry

  1. Store all points in the matrix and mark points other than (r0, c0) as inaccessible
  2. Start the iteration by putting (r0, c0) on the stack, pushing it off the stack into the sorting result array RES, and pushing its four unaccessed cells
  3. Loop until the stack is empty, at which point all cells in the matrix have been accessed and are ranked in res by Manhattan distance

/ * * *@param {number} R
 * @param {number} C
 * @param {number} r0
 * @param {number} c0
 * @return {number[][]}* /
var allCellsDistOrder = function (R, C, r0, c0) {
    const res = []
    // Store the access status of all points
    const visited = new Array(R).fill(0).map(e= >new Array(C).fill(false))
    // Push the start point and change the start point access state
    const q = [[r0, c0]]
    visited[r0][c0] = true
    // The coordinate difference between the four positions of the cell
    const dirs = [[1.0], [...1.0], [0, -1], [0.1]]
    // The loading order causes that the top of the stack must be the current smallest cell
    while (q.length) {
        // Get the top of the stack
        const cur = q.shift()
        const x = cur[0], y = cur[1]
        res.push(cur)
        // Get the top stack cell square cell
        for (let i = 0; i < 4; i++) {
            // The coordinate position of the square cell
            let newX = dirs[i][0] + x, newY = dirs[i][1] + y
            // If the square cell is not visited in the matrix, it is pushed and marked as not visited
            if (newX < R && newX >= 0 && newY >= 0&& newY < C && ! visited[newX][newY]) { q.push([newX, newY]) visited[newX][newY] =true}}}return res
};
Copy the code