Capture Surrounded Regions

medium grid dfs

Problem

Given a grid of 'X' and 'O', flip every region of 'O's that is fully surrounded by 'X' (no path of 'O's reaches the border) into 'X'. Border-connected regions stay 'O'.

Invert the search: from every 'O' on the border, flood-fill connected 'O's and mark them as safe (e.g. 'S'). Once the border floods are done, every remaining 'O' is surrounded — flip it to 'X'. Restore the safe markers back to 'O'.

InputX X X X; X O O X; X X O X; X O X X

OutputX X X X; X X X X; X X X X; X O X X

grid (rows separated by ';', cells X or O)

def solve(board):
    if not board: return
    R, C = len(board), len(board[0])
    def dfs(r, c):
        if r < 0 or c < 0 or r >= R or c >= C: return
        if board[r][c] != "O": return
        board[r][c] = "S"
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
    for r in range(R):
        dfs(r, 0); dfs(r, C-1)
    for c in range(C):
        dfs(0, c); dfs(R-1, c)
    for r in range(R):
        for c in range(C):
            board[r][c] = "X" if board[r][c] == "O" else ("O" if board[r][c] == "S" else "X")

function solve(board) {
  if (!board.length) return;
  const R = board.length, C = board[0].length;
  function dfs(r, c) {
    if (r < 0 || c < 0 || r >= R || c >= C) return;
    if (board[r][c] !== "O") return;
    board[r][c] = "S";
    dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1);
  }
  for (let r = 0; r < R; r++) { dfs(r, 0); dfs(r, C-1); }
  for (let c = 0; c < C; c++) { dfs(0, c); dfs(R-1, c); }
  for (let r = 0; r < R; r++)
    for (let c = 0; c < C; c++)
      board[r][c] = board[r][c] === "S" ? "O" : "X";
}

class Solution {
    int R, C;
    char[][] b;
    public void solve(char[][] board) {
        b = board; R = board.length; if (R == 0) return; C = board[0].length;
        for (int r = 0; r < R; r++) { dfs(r, 0); dfs(r, C-1); }
        for (int c = 0; c < C; c++) { dfs(0, c); dfs(R-1, c); }
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                b[r][c] = b[r][c] == 'S' ? 'O' : 'X';
    }
    void dfs(int r, int c) {
        if (r < 0 || c < 0 || r >= R || c >= C) return;
        if (b[r][c] != 'O') return;
        b[r][c] = 'S';
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1);
    }
}

int R, C;
vector<vector<char>>* B;
void dfs(int r, int c) {
    if (r < 0 || c < 0 || r >= R || c >= C) return;
    if ((*B)[r][c] != 'O') return;
    (*B)[r][c] = 'S';
    dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1);
}
void solve(vector<vector<char>>& board) {
    B = &board; R = board.size(); if (!R) return; C = board[0].size();
    for (int r = 0; r < R; r++) { dfs(r, 0); dfs(r, C-1); }
    for (int c = 0; c < C; c++) { dfs(0, c); dfs(R-1, c); }
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            board[r][c] = board[r][c] == 'S' ? 'O' : 'X';
}

Time: O(R · C) Space: O(R · C) recursion worst case