Question

1030. Matrix Cells in Distance Order

中文文档

Description

You are given four integers row, cols, rCenter, and cCenter. There is a rows x cols matrix and you are on the cell with the coordinates (rCenter, cCenter).

Return _the coordinates of all cells in the matrix, sorted by their distance from _(rCenter, cCenter)_ from the smallest distance to the largest distance_. You may return the answer in any order that satisfies this condition.

The distance between two cells (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|.

 

Example 1:

Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]
Explanation: The distances from (0, 0) to other cells are: [0,1]

Example 2:

Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1
Output: [[0,1],[0,0],[1,1],[1,0]]
Explanation: The distances from (0, 1) 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: rows = 2, cols = 3, rCenter = 1, cCenter = 2
Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
Explanation: The distances from (1, 2) 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]].

 

Constraints:

• 1 <= rows, cols <= 100
• 0 <= rCenter < rows
• 0 <= cCenter < cols

Solutions

Solution 1

class Solution:
  def allCellsDistOrder(
    self, rows: int, cols: int, rCenter: int, cCenter: int
  ) -> List[List[int]]:
    q = deque([[rCenter, cCenter]])
    vis = [[False] * cols for _ in range(rows)]
    vis[rCenter][cCenter] = True
    ans = []
    while q:
      for _ in range(len(q)):
        p = q.popleft()
        ans.append(p)
        for a, b in pairwise((-1, 0, 1, 0, -1)):
          x, y = p[0] + a, p[1] + b
          if 0 <= x < rows and 0 <= y < cols and not vis[x][y]:
            vis[x][y] = True
            q.append([x, y])
    return ans

import java.util.Deque;

class Solution {
  public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
    Deque<int[]> q = new ArrayDeque<>();
    q.offer(new int[] {rCenter, cCenter});
    boolean[][] vis = new boolean[rows][cols];
    vis[rCenter][cCenter] = true;
    int[][] ans = new int[rows * cols][2];
    int[] dirs = {-1, 0, 1, 0, -1};
    int idx = 0;
    while (!q.isEmpty()) {
      for (int n = q.size(); n > 0; --n) {
        var p = q.poll();
        ans[idx++] = p;
        for (int k = 0; k < 4; ++k) {
          int x = p[0] + dirs[k], y = p[1] + dirs[k + 1];
          if (x >= 0 && x < rows && y >= 0 && y < cols && !vis[x][y]) {
            vis[x][y] = true;
            q.offer(new int[] {x, y});
          }
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
    queue<pair<int, int>> q;
    q.emplace(rCenter, cCenter);
    vector<vector<int>> ans;
    bool vis[rows][cols];
    memset(vis, false, sizeof(vis));
    vis[rCenter][cCenter] = true;
    int dirs[5] = {-1, 0, 1, 0, -1};
    while (!q.empty()) {
      for (int n = q.size(); n; --n) {
        auto [i, j] = q.front();
        q.pop();
        ans.push_back({i, j});
        for (int k = 0; k < 4; ++k) {
          int x = i + dirs[k];
          int y = j + dirs[k + 1];
          if (x >= 0 && x < rows && y >= 0 && y < cols && !vis[x][y]) {
            vis[x][y] = true;
            q.emplace(x, y);
          }
        }
      }
    }
    return ans;
  }
};

func allCellsDistOrder(rows int, cols int, rCenter int, cCenter int) (ans [][]int) {
  q := [][]int{{rCenter, cCenter}}
  vis := make([][]bool, rows)
  for i := range vis {
    vis[i] = make([]bool, cols)
  }
  vis[rCenter][cCenter] = true
  dirs := [5]int{-1, 0, 1, 0, -1}
  for len(q) > 0 {
    for n := len(q); n > 0; n-- {
      p := q[0]
      q = q[1:]
      ans = append(ans, p)
      for k := 0; k < 4; k++ {
        x, y := p[0]+dirs[k], p[1]+dirs[k+1]
        if x >= 0 && x < rows && y >= 0 && y < cols && !vis[x][y] {
          vis[x][y] = true
          q = append(q, []int{x, y})
        }
      }
    }
  }
  return
}