Surroudned Regions [DFS Matrix]

130.Surrounded Regions

Depth-First Search

Matrix

Graph

Problem Statement:

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.

Example:

Input:

[["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"]]

Algorithm:

1. Find 'O's on border using DFS
2. Mark these border 'O's and connected ones as 'B'
3. Convert remaining 'O's to 'X's (they're surrounded)
4. Restore 'B's back to 'O's

Complexity:

Time: O(m*n) | Space: O(1) in-place modification

Java Solution:

public void solve(char[][] board) {
    if (board == null || board.length == 0)
        return;

    int rows = board.length, columns = board[0].length;

    // DFS from all Os on the edge of the board mark them with 'B'
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < columns; j++) 
            if ((i == 0 || i == rows - 1 || j == 0 || j == columns - 1) && board[i][j] == 'O') 
                dfs(board, i, j);
    
    // Destroy all surrounded regions by marking them with x
    // Restore all 'B' to 'O'
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < columns; j++) 
            if (board[i][j] == 'B')
                board[i][j] = 'O';
            else if (board[i][j] == 'O')
                board[i][j] = 'X';
}

private void dfs(char[][] board, int i, int j) {
    // Check boundaries and if cell is not 'O'
    if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) return;
    if (board[i][j] != 'O') return;

    // Mark as visited
    board[i][j] = 'B';

    // Check all four directions
    dfs(board, i + 1, j);
    dfs(board, i, j + 1);
    dfs(board, i - 1, j);
    dfs(board, i, j - 1);
}

Python Solution:

def solve(self, board: List[List[str]]) -> None:
    if not board: return
    
    rows, cols = len(board), len(board[0])
    
    def dfs(i: int, j: int) -> None:
        if i < 0 or j < 0 or i >= rows or j >= cols:
            return
        if board[i][j] != 'O':
            return
            
        board[i][j] = 'B'
        
        for di, dj in [(1,0), (0,1), (-1,0), (0,-1)]:
            dfs(i + di, j + dj)
    
    # Mark border O's and connected ones
    for i in range(rows):
        for j in range(cols):
            if (i in [0, rows-1] or j in [0, cols-1]) and board[i][j] == 'O':
                dfs(i, j)
    
    # Flip remaining O's and restore B's
    for i in range(rows):
        for j in range(cols):
            if board[i][j] == 'B':
                board[i][j] = 'O'
            elif board[i][j] == 'O':
                board[i][j] = 'X'

C++ Solution:

class Solution {
public:
    void solve(vectorchar>>& board) {
        if (board.empty()) return;
        
        int rows = board.size(), cols = board[0].size();
        
        // Check borders first
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if ((i == 0 || i == rows-1 || j == 0 || j == cols-1) && 
                    board[i][j] == 'O')
                    dfs(board, i, j);
            }
        }
        
        // Process remaining cells
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'B')
                    board[i][j] = 'O';
                else if (board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }
    
private:
    void dfs(vectorchar>>& board, int i, int j) {
        if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size()) 
            return;
        if (board[i][j] != 'O') return;
        
        board[i][j] = 'B';
        
        dfs(board, i+1, j);
        dfs(board, i, j+1);
        dfs(board, i-1, j);
        dfs(board, i, j-1);
    }
};