# 1030. Matrix Cells in Distance Order¶

• Time: $O(\texttt{rows} \cdot \texttt{cols})$
• Space: $O(\texttt{rows} \cdot \texttt{cols})$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public: vector> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) { constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; vector> ans; vector> seen(rows, vector(cols)); queue> q{{{rCenter, cCenter}}}; seen[rCenter][cCenter] = true; while (!q.empty()) { const auto [i, j] = q.front(); q.pop(); ans.push_back({i, j}); for (const auto& [dx, dy] : dirs) { const int x = i + dx; const int y = j + dy; if (x < 0 || x == rows || y < 0 || y == cols) continue; if (seen[x][y]) continue; seen[x][y] = true; q.emplace(x, y); } } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) { final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; List ans = new ArrayList<>(); boolean[][] seen = new boolean[rows][cols]; Queue> q = new LinkedList<>(Arrays.asList(new Pair<>(rCenter, cCenter))); seen[rCenter][cCenter] = true; while (!q.isEmpty()) { final int i = q.peek().getKey(); final int j = q.poll().getValue(); ans.add(new int[] {i, j}); for (int[] dir : dirs) { final int x = i + dir[0]; final int y = j + dir[1]; if (x < 0 || x == rows || y < 0 || y == cols) continue; if (seen[x][y]) continue; seen[x][y] = true; q.offer(new Pair<>(x, y)); } } return ans.toArray(int[][] ::new); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution: def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]: dirs = ((0, 1), (1, 0), (0, -1), (-1, 0)) ans = [] q = collections.deque([(rCenter, cCenter)]) seen = {(rCenter, cCenter)} while q: i, j = q.popleft() ans.append([i, j]) for dx, dy in dirs: x = i + dx y = j + dy if x < 0 or x == rows or y < 0 or y == cols: continue if (x, y) in seen: continue seen.add((x, y)) q.append((x, y)) return ans