Marauder Bot

Problem

You are given a grid of cells marked either captured territory or open region. Any connected group of open cells (linked horizontally or vertically) that is completely enclosed by captured territory should itself be flipped into captured territory. A group that touches the border of the grid anywhere, even through a long chain of connections, escapes capture and stays as it is.

Example. An open cell tucked in the middle of the grid and fully ringed by captured cells gets flipped, while an open cell on the top row, and anything connected to it, remains untouched.

Key idea

Checking, for every open region, whether it eventually touches the border would mean re-walking large parts of the grid repeatedly. It is cheaper to flip the question: any open cell connected to the border can never be captured, no matter how convoluted the chain, so find all such safe cells first. Flood fill outward starting from every open cell on the border, marking every cell reached as safe. A single pass over the grid then finishes the job: any open cell never marked safe must be enclosed, so flip it to captured, and any cell marked safe simply reverts to its original open state.

Solution

function solve(board: string[][]): void {
  const rows = board.length;
  const cols = board[0].length;
  const SAFE = '#'; // temporary marker for open cells connected to the border

  function flood(row: number, col: number): void {
    if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] !== 'O') {
      return;
    }
    board[row][col] = SAFE;
    flood(row + 1, col);
    flood(row - 1, col);
    flood(row, col + 1);
    flood(row, col - 1);
  }

  // flood inward from every open cell on the border first
  for (let row = 0; row < rows; row++) {
    flood(row, 0);
    flood(row, cols - 1);
  }
  for (let col = 0; col < cols; col++) {
    flood(0, col);
    flood(rows - 1, col);
  }

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (board[row][col] === 'O') {
        board[row][col] = 'X'; // never reached from the border: enclosed, so capture it
      } else if (board[row][col] === SAFE) {
        board[row][col] = 'O'; // border-connected: revert back to open
      }
    }
  }
}

Complexity

Time: O(rows × cols). The boundary flood fill and the final sweep each touch every cell at most once.
Space: O(rows × cols). For the safe markings and the recursion or queue used during flood fill.

Watch out for

Start the flood fill only from open cells already on the border, not from every open cell in the grid.
Use a temporary marker for safe that is distinct from both symbols, and convert it back to the open symbol at the end.
On large grids, an iterative breadth-first search avoids the recursion-depth issues a deep depth-first search can hit.

Pattern

This is the same boundary-seeded flood fill used in Pacific Atlantic Water Flow: flood inward from the edges to find what cannot be affected, then treat everything else as the answer.

Surrounded Regions