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

题目

给出 R 行 C 列的矩阵，其中的单元格的整数坐标为 (r, c)，满足 0 <= r < R 且 0 <= c < C。

另外，我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。

返回矩阵中的所有单元格的坐标，并按到 (r0, c0) 的距离从最小到最大的顺序排，其中，两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离，|r1 - r2| + |c1 - c2|。（你可以按任何满足此条件的顺序返回答案。）

示例

输入：R = 1, C = 2, r0 = 0, c0 = 0 输出：[[0,0],[0,1]]

输入：R = 2, C = 2, r0 = 0, c0 = 1 输出：[[0,1],[0,0],[1,1],[1,0]]

输入：R = 2, C = 3, r0 = 1,c0 = 2 输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]

提示

• 1 <= R <= 100
• 1 <= C <= 100
• 0 <= r0 < R
• 0 <= c0 < C

算法

使用sort排序

先将矩阵中所有点遍历出来，然后排序

export const allCellsDistOrder = (R, C, r0, c0) => {
	const points = [];
	for (let r = 0; r < R; r++) {
		for (let c = 0; c < C; c++) {
			points.push([r, c]);
		}
	}
	points.sort((a, b) => {
		const distanceA = Math.abs(a[0] - r0) + Math.abs(a[1] - c0);
		const distanceB = Math.abs(b[0] - r0) + Math.abs(b[1] - c0);
		return distanceA - distanceB;
	});
	return points;
};

桶排序

每个桶中放入距离相同的点，桶的下标（数组中每一项）为桶中点的距离，然后合并这些桶（因为满足距离相同即可，所以桶中不必排序）

export const allCellsDistOrder = (R, C, r0, c0) => {
	const disArr = [];
	for (let r = 0; r < R; r++) {
		for (let c = 0; c < C; c++) {
			const distance = Math.abs(r0 - r) + Math.abs(c0 - c);
			disArr[disArr] ? disArr[distance].push([r, c]) : (disArr[distance] = [[r, c]]);
		}
	}
	const res = [];
	disArr.forEach((item) => {
		res.push(...item);
	});
	return res;
};

BFS

曼哈顿距离阵列如下图：

5 4 3 2 3 4 5
4 3 2 1 2 3 4
3 2 1 0 1 2 3
4 3 2 1 2 3 4
5 4 3 2 3 4 5

可以看到距离较给定点（r0,c0）扩散向外增大，即我们不需要求距离并比较，从点(r0,c0)依次向外查找点推入结果数组，且过滤掉已经推入结果的点，最后就能得到结果

• 创建一个和位置阵列相同行列数的矩阵visited，用来存储某个位置的点是否已经被放入结果数组，防止重复取点。初始全部填充false，将目标点位置visited[r0][c0]设置为true
• 初始化一个队列queue用来存放遍历到的相邻的有效的点，默认填充目标点[r0,c0]
• 每次取出队列queue中的第一个点，推入结果数组res，然后以这个点为中心判断上下左右四个方向的点是否在范围内、是否不在queue或res中，如果都满足则推入队列queue作为之后待判断的中心点；这样队列queue可以保证每次从队列头取出的元素都是距离依次递增的（因为推入queue尾的时候就是按照上下左右的顺序从内向外推入的）
• 直到队列queue为空时，跳出循环，返回结果res

export const allCellsDistOrder = (R, C, r0, c0) => {
	const visited = new Array(R).fill(0).map(() => new Array(C).fill(false));
	visited[r0][c0] = true;
	const queue = [[r0, c0]];
	const res = [];
	while (queue.length) {
		const point = queue.shift();
		res.push(point);
		const x = point[0],
			y = point[1];
		visited[x][y] = true;
		if (y - 1 >= 0 && !visited[x][y - 1]) {
			queue.push([x, y - 1]);
			visited[x][y - 1] = true;
		}
		if (y + 1 < C && !visited[x][y + 1]) {
			queue.push([x, y + 1]);
			visited[x][y + 1] = true;
		}
		if (x - 1 >= 0 && !visited[x - 1][y]) {
			queue.push([x - 1, y]);
			visited[x - 1][y] = true;
		}
		if (x + 1 < R && !visited[x + 1][y]) {
			queue.push([x + 1, y]);
			visited[x + 1][y] = true;
		}
	}
	return res;
};