Algorithm
Problem Name: 1030. Matrix Cells in Distance Order
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 <= 1000 <= rCenter < rows0 <= cCenter < cols
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
int[][] points = new int[R * C][2];
Queue < int[]> queue = new LinkedList<>();
int idx = 0;
queue.add(new int[]{r0, c0});
boolean[][] visited = new boolean[R][C];
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int r = curr[0];
int c = curr[1];
if (r < 0 || r >= R || c < 0 || c >= C || visited[r][c]) {
continue;
}
points[idx++] = curr;
visited[r][c] = true;
queue.add(new int[]{r, c - 1});
queue.add(new int[]{r, c + 1});
queue.add(new int[]{r - 1, c});
queue.add(new int[]{r + 1, c});
}
return points;
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const allCellsDistOrder = function(R, C, r0, c0) {
const matrix = Array.from({ length: R }, () => new Array(C))
const arr = []
for (let i = 0; i < R; i++) {
for (let j = 0; j < C; j++) {
arr.push([i, j])
}
}
return arr.sort(
(a, b) =>
Math.abs(a[0] - r0) +
Math.abs(a[1] - c0) -
(Math.abs(b[0] - r0) + Math.abs(b[1] - c0))
)
}
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
bfs, res, seen = [[r0, c0]], [], {(r0, c0)}
while bfs:
res += bfs
new = []
for i, j in bfs:
for x, y in (i - 1, j), (i + 1, j), (i, j + 1), (i, j - 1):
if 0 <= x < R and 0 <= y < C and (x, y) not in seen:
seen.add((x, y))
new.append([x, y])
bfs = new
return res
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _1030_MatrixCellsInDistanceOrder
{
public int[][] AllCellsDistOrder(int R, int C, int r0, int c0)
{
(int, int)[] directions = { (0, 1), (0, -1), (1, 0), (-1, 0) };
var bfs = new Queue < (int, int)>();
var visited = new bool[R, C];
var result = new int[R * C][];
int index = 0;
bfs.Enqueue((r0, c0));
visited[r0, c0] = true;
while (bfs.Count > 0)
{
var node = bfs.Dequeue();
result[index++] = new int[2] { node.Item1, node.Item2 };
foreach (var direction in directions)
{
int newRow = node.Item1 + direction.Item1;
int newCol = node.Item2 + direction.Item2;
if (newRow >= 0 && newRow < R && newCol >= 0 && newCol < C && !visited[newRow, newCol])
{
bfs.Enqueue((newRow, newCol));
visited[newRow, newCol] = true;
}
}
}
return result;
}
}
}
Input
Output