# 1030. Matrix Cells in Distance Order

• Time: $O(n)$
• Space: $O(n)$
  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) { const vector dirs{0, 1, 0, -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 (int k = 0; k < 4; ++k) { const int x = i + dirs[k]; const int y = j + dirs[k + 1]; 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, 0, -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 k = 0; k < 4; ++k) { final int x = i + dirs[k]; final int y = j + dirs[k + 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, 0, -1, 0] ans = [] q = collections.deque([(rCenter, cCenter)]) seen = {(rCenter, cCenter)} while q: i, j = q.popleft() ans.append([i, j]) for k in range(4): x = i + dirs[k] y = j + dirs[k + 1] 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