1030. Matrix Cells in Distance Order

# 1030. Matrix Cells in Distance Order#

## 题目 #

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

## 解题思路 #

• 按照题意计算矩阵内给定点到其他每个点的距离即可

## 代码 #

``````
package leetcode

func allCellsDistOrder(R int, C int, r0 int, c0 int) [][]int {
longRow, longCol, result := max(abs(r0-0), abs(R-r0)), max(abs(c0-0), abs(C-c0)), make([][]int, 0)
maxDistance := longRow + longCol
bucket := make([][][]int, maxDistance+1)
for i := 0; i <= maxDistance; i++ {
bucket[i] = make([][]int, 0)
}
for r := 0; r < R; r++ {
for c := 0; c < C; c++ {
distance := abs(r-r0) + abs(c-c0)
tmp := []int{r, c}
bucket[distance] = append(bucket[distance], tmp)
}
}
for i := 0; i <= maxDistance; i++ {
for _, buk := range bucket[i] {
result = append(result, buk)
}
}
return result
}

`````` Jun 22, 2022 Edit this page