Surrounded Regions — Boundary DFS

Problem

Given an m x n board of 'X' and 'O', capture all regions surrounded by 'X' (flip enclosed 'O' to 'X'). Regions touching the border are never captured.

Approach — Boundary DFS (3-step)

Mark all 'O' reachable from border as 'S' (safe)
Flip all remaining 'O' → 'X'
Flip all 'S' → 'O'

Time: O(mn) | Space: O(mn)

Solutions

C++

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

Java

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

Python

class Solution:
    def solve(self, board: list[list[str]]) -> None:
        R,C=len(board),len(board[0])
        def dfs(r,c):
            if not(0<=r<R and 0<=c<C) or board[r][c]!='O': return
            board[r][c]='S'
            for dr,dc in[(1,0),(-1,0),(0,1),(0,-1)]: dfs(r+dr,c+dc)
        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):
                if board[r][c]=='O': board[r][c]='X'
                elif board[r][c]=='S': board[r][c]='O'

Complexity

Time: O(mn) | Space: O(mn)

Key Takeaway

Boundary DFS pattern: mark border-reachable cells, then process unmarked interior cells.