Crack the Backend

Problem Statement

Given an m×n board containing 'X' and 'O', capture all regions that are surrounded by 'X'. A region is surrounded if all 'O' in it are not on the border and are not 4-directionally connected to an 'O' on the border. To "capture" means to flip all 'O' in that region to 'X'. Do not capture 'O' that are on the border or connected to the border.

Reverse: Instead of finding surrounded regions, find all 'O' that are connected to the border (directly or through other 'O'). Mark them (e.g. temporarily as 'T'). Then: any 'O' that was not marked is surrounded — flip it to 'X'. Finally restore the marked cells back to 'O'.

Key Observations

DFS/BFS from border: For each cell on the border (r=0, r=m-1, c=0, c=n-1) that is 'O', start DFS/BFS and mark every connected 'O' (e.g. set to 'T'). Then iterate the whole board: if board[r][c] == 'T', set to 'O'; if board[r][c] == 'O', set to 'X'. We can do the marking in place by using a non-letter character.

Approach

High-level: From every border cell that is 'O', DFS/BFS and mark all connected 'O' as 'T'. Then for all cells: if 'T' set to 'O'; if 'O' set to 'X'.

Steps: For (r,c) on border with board[r][c]=='O', dfs(r,c): if out of bounds or not 'O' return; board[r][c]='T'; dfs 4 neighbors. Then double loop: if board[i][j]=='T' board[i][j]='O'; else if board[i][j]=='O' board[i][j]='X'.

Implementation

Java

public void solve(char[][] board) {
    int m = board.length, n = board[0].length;

    for (int i = 0; i < m; i++) {
        if (board[i][0] == 'O') {
            dfs(board, i, 0);
        }

        if (board[i][n-1] == 'O') {
            dfs(board, i, n-1);
        }
    }

    for (int j = 0; j < n; j++) {
        if (board[0][j] == 'O') {
            dfs(board, 0, j);
        }

        if (board[m-1][j] == 'O') {
            dfs(board, m-1, j);
        }
    }

    for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++) {
        if (board[i][j] == 'T') {
            board[i][j] = 'O';
        }
        else if (board[i][j] == 'O') {
            board[i][j] = 'X';
        }
    }
}

void dfs(char[][] b, int r, int c) {

    if (r<0||r>=b.length||c<0||c>=b[0].length||b[r][c]!='O') {
        return;
    }

    b[r][c] = 'T';
    dfs(b,r+1,c); dfs(b,r-1,c); dfs(b,r,c+1); dfs(b,r,c-1);
}

Test Cases

Example 1

Input

board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

Expected

Middle O captured

Explanation

Only border-connected O remain.

Complexity Analysis

Time: O(m*n).
Space: O(m*n).

Follow-ups

Count captured regions.