# 130. Surrounded Regions       ## Approach 1: BFS

• Time: $O(mn)$
• Space: $O(1)$
  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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution { public: void solve(vector>& board) { if (board.empty()) return; const int m = board.size(); const int n = board.size(); const vector dirs{0, 1, 0, -1, 0}; queue> q; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (i * j == 0 || i == m - 1 || j == n - 1) if (board[i][j] == 'O') { q.emplace(i, j); board[i][j] = '*'; } // Mark the grids that stretch from the four sides with '*'. while (!q.empty()) { const auto [i, j] = q.front(); q.pop(); for (int k = 0; k < 4; ++k) { const int x = i + dirs[k]; const int y = j + dirs[k + 1]; if (x < 0 || x == m || y < 0 || y == n) continue; if (board[x][y] != 'O') continue; q.emplace(x, y); board[x][y] = '*'; } } for (vector& row : board) for (char& c : row) if (c == '*') c = 'O'; else if (c == 'O') c = 'X'; } }; 
  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 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution { public void solve(char[][] board) { if (board.length == 0) return; final int m = board.length; final int n = board.length; final int[] dirs = {0, 1, 0, -1, 0}; Queue q = new ArrayDeque<>(); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (i * j == 0 || i == m - 1 || j == n - 1) if (board[i][j] == 'O') { q.offer(new int[] {i, j}); board[i][j] = '*'; } // Mark the grids that stretch from the four sides with '*'. while (!q.isEmpty()) { final int i = q.peek(); final int j = q.poll(); for (int k = 0; k < 4; ++k) { final int x = i + dirs[k]; final int y = j + dirs[k + 1]; if (x < 0 || x == m || y < 0 || y == n) continue; if (board[x][y] != 'O') continue; q.offer(new int[] {x, y}); board[x][y] = '*'; } } for (char[] row : board) for (int i = 0; i < row.length; ++i) if (row[i] == '*') row[i] = 'O'; else if (row[i] == 'O') row[i] = 'X'; } } 
  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 30 31 32 33 class Solution: def solve(self, board: List[List[str]]) -> None: if not board: return m = len(board) n = len(board) dirs = [0, 1, 0, -1, 0] q = collections.deque() for i in range(m): for j in range(n): if i * j == 0 or i == m - 1 or j == n - 1: if board[i][j] == 'O': q.append((i, j)) board[i][j] = '*' # Mark the grids that stretch from the four sides with '*'. while q: i, j = q.popleft() for k in range(4): x = i + dirs[k] y = j + dirs[k + 1] if x < 0 or x == m or y < 0 or y == n: continue if board[x][y] != 'O': continue q.append((x, y)) board[x][y] = '*' for row in board: for i, c in enumerate(row): row[i] = 'O' if c == '*' else 'X' 

## Approach 2: DFS

• Time: $O(mn)$
• Space: $O(1)$
  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 30 31 32 33 34 35 36 class Solution { public: void solve(vector>& board) { if (board.empty()) return; const int m = board.size(); const int n = board.size(); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (i * j == 0 || i == m - 1 || j == n - 1) dfs(board, i, j); for (vector& row : board) for (char& c : row) if (c == '*') c = 'O'; else if (c == 'O') c = 'X'; } private: // Marks the grids with 'O' that stretch from the four sides to '*'. void dfs(vector>& board, int i, int j) { if (i < 0 || i == board.size() || j < 0 || j == board.size()) return; if (board[i][j] != 'O') return; board[i][j] = '*'; dfs(board, i + 1, j); dfs(board, i - 1, j); dfs(board, i, j + 1); dfs(board, i, j - 1); } }; 
  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 30 31 32 33 34 class Solution { public void solve(char[][] board) { if (board.length == 0) return; final int m = board.length; final int n = board.length; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (i * j == 0 || i == m - 1 || j == n - 1) dfs(board, i, j); for (char[] row : board) for (int i = 0; i < row.length; ++i) if (row[i] == '*') row[i] = 'O'; else if (row[i] == 'O') row[i] = 'X'; } // Marks the grids with 'O' that stretch from the four sides to '*'. private void dfs(char[][] board, int i, int j) { if (i < 0 || i == board.length || j < 0 || j == board.length) return; if (board[i][j] != 'O') return; board[i][j] = '*'; dfs(board, i + 1, j); dfs(board, i - 1, j); dfs(board, i, j + 1); dfs(board, i, j - 1); } } 
  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 class Solution: def solve(self, board: List[List[str]]) -> None: if not board: return m = len(board) n = len(board) def dfs(i: int, j: int) -> None: """Marks the grids with 'O' that stretch from the four sides to '*'.""" if i < 0 or i == m or j < 0 or j == n: return if board[i][j] != 'O': return board[i][j] = '*' dfs(i + 1, j) dfs(i - 1, j) dfs(i, j + 1) dfs(i, j - 1) for i in range(m): for j in range(n): if i * j == 0 or i == m - 1 or j == n - 1: dfs(i, j) for row in board: for i, c in enumerate(row): row[i] = 'O' if c == '*' else 'X'