題目

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

題目大意

給出 R 行 C 列的矩陣，其中的單元格的整數座標為 (r, c)，滿足 0 <= r < R 且 0 <= c < C。另外，我們在該矩陣中給出了一個座標為 (r0, c0) 的單元格。

返回矩陣中的所有單元格的座標，並按到 (r0, c0) 的距離從最小到最大的順序排，其中，兩單元格(r1, c1) 和 (r2, c2) 之間的距離是曼哈頓距離，|r1 - r2| + |c1 - c2|。（你可以按任何滿足此條件的順序返回答案。）

解題思路

  • 按照題意計算矩陣內給定點到其他每個點的距離即可

�離即可

參考代碼

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
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}