Skip to content
AI360Xpert
Back to Graphs
Medium

Surrounded Regions

Given an `m x n` matrix `board` containing `'X'` and `'O'`, capture all regions that are 4-directionally surrounded by `'X'`. A region is captured by flipping all `'O'`s into `'X'`s in that surrounded region.

Examples

Input:board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output:[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Notice that an 'O' should not be flipped if: - It is on the border, or - It is adjacent to an 'O' that should not be flipped. The bottom 'O' is on the border, so it is not flipped. The other three 'O' form a surrounded region, so they are flipped.
Input:board = [["X"]]
Output:[["X"]]
No surrounded regions to capture.

Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] is 'X' or 'O'.

Reverse Thinking (DFS)

Approach

Instead of trying to find surrounded regions, it is easier to find the regions that are NOT surrounded. An 'O' region is not surrounded if it connects to the border. We iterate through the border of the board. Whenever we find an 'O', we run DFS from it to find all connected 'O's, marking them temporarily as 'T' (or any other character). After checking all borders, any remaining 'O' must be completely surrounded, so we flip it to 'X'. Finally, we revert the temporarily marked 'T's back to 'O's.

Complexity Analysis

Time Complexity
O(m * n)
Space Complexity
O(m * n)

Time complexity is O(m * n) as we visit each cell at most a constant number of times. Space complexity is O(m * n) in the worst case for the DFS call stack.

Solution.java
class Solution {    public void solve(char[][] board) {        if (board == null || board.length == 0) return;                int m = board.length;        int n = board[0].length;                // Step 1: Mark unsurrounded 'O's connected to borders as 'T'        for (int i = 0; i < m; i++) {            dfs(board, i, 0); // Left border            dfs(board, i, n - 1); // Right border        }        for (int j = 0; j < n; j++) {            dfs(board, 0, j); // Top border            dfs(board, m - 1, j); // Bottom border        }                // Step 2: Flip remaining 'O's to 'X' and 'T's back to 'O'        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (board[i][j] == 'O') {                    board[i][j] = 'X'; // Captured                } else if (board[i][j] == 'T') {                    board[i][j] = 'O'; // Reverted                }            }        }    }        private void dfs(char[][] board, int r, int c) {        int m = board.length;        int n = board[0].length;                if (r < 0 || c < 0 || r >= m || c >= n || board[r][c] != 'O') {            return;        }                board[r][c] = 'T'; // Mark as temporary                dfs(board, r + 1, c);        dfs(board, r - 1, c);        dfs(board, r, c + 1);        dfs(board, r, c - 1);    }}