1030. 距离顺序排列矩阵单元格

🟢   🔖  几何 数组 数学 矩阵 排序  🔗 力扣 LeetCode

题目

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

题目大意

给定四个整数 rows , cols , rCenter 和 cCenter 。有一个 rows x cols 的矩阵，你在单元格上的坐标是 (rCenter, cCenter) 。

返回矩阵中的所有单元格的坐标，并按与 (rCenter, cCenter) 的 距离 从最小到最大的顺序排。你可以按 任何 满足此条件的顺序返回答案。

单元格(r1, c1) 和 (r2, c2) 之间的距离为|r1 - r2| + |c1 - c2|。

示例 1：

输入： rows = 1, cols = 2, rCenter = 0, cCenter = 0

输出：[[0,0],[0,1]]

解释 ：从 (r0, c0) 到其他单元格的距离为：[0,1]

示例 2：

输入： rows = 2, cols = 2, rCenter = 0, cCenter = 1

输出：[[0,1],[0,0],[1,1],[1,0]]

解释 ：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]

[[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。

示例 3：

输入： rows = 2, cols = 3, rCenter = 1, cCenter = 2

输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]

解释 ：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]

其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。

提示：

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

解题思路

可以使用 BFS（广度优先搜索）来解决这个问题。

• 以 (rCenter, cCenter) 为 BFS 起点，其距离为 0。
• 从起点开始，依次访问其四周的单元格（上下左右），并将这些单元格加入队列。
• 每访问一个单元格时，记录其坐标，并标记为已访问，使用一个集合（或矩阵）标记已访问单元格，避免重复访问。
• 按照层级遍历，依次从近到远处理所有单元格。

复杂度分析

• 时间复杂度：O(rows * cols)，每个单元格最多会被访问一次，且访问过程中的操作（入队、出队、添加到结果集）均为常数时间。
• 空间复杂度：O(rows * cols)
  • 需要一个队列来存储当前的节点，队列的最大大小为单元格总数：O(rows * cols)
  • 还需要一个 visited 数组，用于标记访问状态，空间复杂度同样为：O(rows * cols)

代码

/**
 * @param {number} rows
 * @param {number} cols
 * @param {number} rCenter
 * @param {number} cCenter
 * @return {number[][]}
 */
var allCellsDistOrder = function (rows, cols, rCenter, cCenter) {
	const directions = [
		[1, 0],
		[-1, 0],
		[0, 1],
		[0, -1]
	]; // 上下左右四个方向
	const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
	const result = [];
	const queue = [[rCenter, cCenter]]; // BFS 队列，从中心点开始
	visited[rCenter][cCenter] = true;

	while (queue.length > 0) {
		const [r, c] = queue.shift();
		result.push([r, c]); // 记录当前单元格

		// 遍历四个方向
		for (const [dr, dc] of directions) {
			const nr = r + dr,
				nc = c + dc;
			// 检查边界和是否已访问
			if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc]) {
				visited[nr][nc] = true;
				queue.push([nr, nc]);
			}
		}
	}

	return result;
};

相关题目

题号	标题	题解	标签	难度	力扣
2194	Excel 表中某个范围内的单元格	[✓]	字符串	🟢	🀄️ 🔗