130. Surrounded Regions

Problem Description

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

Example 1:
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"]]
Explanation: 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.

Example 2:
Input: board = [["X"]]
Output: [["X"]]

def solve(board: List[List[str]]) -> None:
    """
    Do not return anything, modify board in-place instead.
    """
    if not board or not board[0]:
        return
    
    rows, cols = len(board), len(board[0])
    
    def dfs(i: int, j: int) -> None:
        if i < 0 or i >= rows or j < 0 or j >= cols or board[i][j] != 'O':
            return
        
        # Mark as visited
        board[i][j] = '#'
        
        # Check all 4 directions
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    
    # Check borders
    for i in range(rows):
        dfs(i, 0)
        dfs(i, cols-1)
    
    for j in range(cols):
        dfs(0, j)
        dfs(rows-1, j)
    
    # Convert remaining 'O's to 'X's and '#'s back to 'O's
    for i in range(rows):
        for j in range(cols):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            elif board[i][j] == '#':
                board[i][j] = 'O'

class Solution {
    private int rows, cols;
    
    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        
        rows = board.length;
        cols = board[0].length;
        
        // Check borders
        for (int i = 0; i < rows; i++) {
            dfs(board, i, 0);
            dfs(board, i, cols-1);
        }
        
        for (int j = 0; j < cols; j++) {
            dfs(board, 0, j);
            dfs(board, rows-1, j);
        }
        
        // Convert remaining 'O's to 'X's and '#'s back to 'O's
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    private void dfs(char[][] board, int i, int j) {
        if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] != 'O') {
            return;
        }
        
        // Mark as visited
        board[i][j] = '#';
        
        // Check all 4 directions
        dfs(board, i+1, j);
        dfs(board, i-1, j);
        dfs(board, i, j+1);
        dfs(board, i, j-1);
    }
}

class Solution {
private:
    int rows, cols;
    
    void dfs(vector>& board, int i, int j) {
        if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] != 'O') {
            return;
        }
        
        // Mark as visited
        board[i][j] = '#';
        
        // Check all 4 directions
        dfs(board, i+1, j);
        dfs(board, i-1, j);
        dfs(board, i, j+1);
        dfs(board, i, j-1);
    }
    
public:
    void solve(vector>& board) {
        if (board.empty() || board[0].empty()) {
            return;
        }
        
        rows = board.size();
        cols = board[0].size();
        
        // Check borders
        for (int i = 0; i < rows; i++) {
            dfs(board, i, 0);
            dfs(board, i, cols-1);
        }
        
        for (int j = 0; j < cols; j++) {
            dfs(board, 0, j);
            dfs(board, rows-1, j);
        }
        
        // Convert remaining 'O's to 'X's and '#'s back to 'O's
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
};

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function(board) {
    if (!board || !board[0]) {
        return;
    }
    
    const rows = board.length;
    const cols = board[0].length;
    
    const dfs = (i, j) => {
        if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] !== 'O') {
            return;
        }
        
        // Mark as visited
        board[i][j] = '#';
        
        // Check all 4 directions
        dfs(i+1, j);
        dfs(i-1, j);
        dfs(i, j+1);
        dfs(i, j-1);
    };
    
    // Check borders
    for (let i = 0; i < rows; i++) {
        dfs(i, 0);
        dfs(i, cols-1);
    }
    
    for (let j = 0; j < cols; j++) {
        dfs(0, j);
        dfs(rows-1, j);
    }
    
    // Convert remaining 'O's to 'X's and '#'s back to 'O's
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (board[i][j] === 'O') {
                board[i][j] = 'X';
            } else if (board[i][j] === '#') {
                board[i][j] = 'O';
            }
        }
    }
};

public class Solution {
    private int rows, cols;
    
    public void Solve(char[][] board) {
        if (board == null || board.Length == 0) {
            return;
        }
        
        rows = board.Length;
        cols = board[0].Length;
        
        // Check borders
        for (int i = 0; i < rows; i++) {
            DFS(board, i, 0);
            DFS(board, i, cols-1);
        }
        
        for (int j = 0; j < cols; j++) {
            DFS(board, 0, j);
            DFS(board, rows-1, j);
        }
        
        // Convert remaining 'O's to 'X's and '#'s back to 'O's
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    private void DFS(char[][] board, int i, int j) {
        if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] != 'O') {
            return;
        }
        
        // Mark as visited
        board[i][j] = '#';
        
        // Check all 4 directions
        DFS(board, i+1, j);
        DFS(board, i-1, j);
        DFS(board, i, j+1);
        DFS(board, i, j-1);
    }
}