Surrounded Regions

medium grid dfs

Problem

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

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';
}

Explanation

The clever idea here is to invert the question. Instead of hunting for the Os that are trapped, we find the ones that are safe — and an O is safe exactly when it connects to the border. Any O not reachable from the edge must be surrounded.

So we start a flood fill (DFS) from every O sitting on the board's border. Each O we can reach gets temporarily marked S for safe, and the search spreads to its up/down/left/right neighbors that are also O.

The dfs(r, c) function stops if it walks off the grid or hits a cell that isn't an O; otherwise it stamps S and recurses in four directions. We call it along all four edges of the board.

After flooding, one final sweep cleans up: any cell still showing O was never reached from the border, so it is surrounded and becomes X; any S is restored to O.

Example: in the middle of the board an O region with no path to the edge is flipped to X, while the O on the bottom row touches the border, stays safe, and remains O.

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