Capture the enclosed regions

def capture_regions(board):
    rows, cols = len(board), len(board[0])
    g = [list(row) for row in board]
    safe = [[False] * cols for _ in range(rows)]
    stack = [(r, c) for r in range(rows) for c in range(cols)
             if (r in (0, rows - 1) or c in (0, cols - 1)) and g[r][c] == 'O']
    for r, c in stack:
        safe[r][c] = True               # every border O is safe
    while stack:                        # flood inwards from all of them at once
        r, c = stack.pop()
        for a, b in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= a < rows and 0 <= b < cols and g[a][b] == 'O' and not safe[a][b]:
                safe[a][b] = True
                stack.append((a, b))
    return [''.join('X' if g[r][c] == 'O' and not safe[r][c] else g[r][c] for c in range(cols))
            for r in range(rows)]

#include <string>
#include <utility>
#include <vector>

std::vector<std::string> solve(std::vector<std::string> board) {
    const int rows = board.size(), cols = board[0].size();
    std::vector<std::vector<bool>> safe(rows, std::vector<bool>(cols, false));
    std::vector<std::pair<int, int>> stack;
    for (int r = 0; r < rows; ++r)
        for (int c = 0; c < cols; ++c) {
            bool border = r == 0 || c == 0 || r == rows - 1 || c == cols - 1;
            if (border && board[r][c] == 'O') { safe[r][c] = true; stack.push_back({r, c}); }
        }
    const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    while (!stack.empty()) {                 // flood inwards from every border O
        auto [r, c] = stack.back();
        stack.pop_back();
        for (int k = 0; k < 4; ++k) {
            int a = r + dr[k], b = c + dc[k];
            if (a >= 0 && b >= 0 && a < rows && b < cols && board[a][b] == 'O' && !safe[a][b]) {
                safe[a][b] = true;
                stack.push_back({a, b});
            }
        }
    }
    for (int r = 0; r < rows; ++r)
        for (int c = 0; c < cols; ++c)
            if (board[r][c] == 'O' && !safe[r][c]) board[r][c] = 'X';
    return board;
}

import java.util.*;

class Solution {
    public String[] captureRegions(String[] board) {
        int rows = board.length, cols = board[0].length();
        char[][] g = new char[rows][];
        for (int r = 0; r < rows; r++) g[r] = board[r].toCharArray();
        boolean[][] safe = new boolean[rows][cols];
        ArrayDeque<int[]> stack = new ArrayDeque<>();
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++) {
                boolean border = r == 0 || c == 0 || r == rows - 1 || c == cols - 1;
                if (border && g[r][c] == 'O') { safe[r][c] = true; stack.push(new int[]{r, c}); }
            }
        int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
        while (!stack.isEmpty()) {               // flood inwards from every border O
            int[] cell = stack.pop();
            for (int k = 0; k < 4; k++) {
                int a = cell[0] + dr[k], b = cell[1] + dc[k];
                if (a >= 0 && b >= 0 && a < rows && b < cols && g[a][b] == 'O' && !safe[a][b]) {
                    safe[a][b] = true;
                    stack.push(new int[]{a, b});
                }
            }
        }
        String[] out = new String[rows];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) if (g[r][c] == 'O' && !safe[r][c]) g[r][c] = 'X';
            out[r] = new String(g[r]);
        }
        return out;
    }
}

function captureRegions(board) {
  const rows = board.length, cols = board[0].length;
  const safe = Array.from({ length: rows }, () => new Array(cols).fill(false));
  const stack = [];
  for (let r = 0; r < rows; r++) for (let c = 0; c < cols; c++) {
    const border = r === 0 || c === 0 || r === rows - 1 || c === cols - 1;
    if (border && board[r][c] === 'O') { safe[r][c] = true; stack.push([r, c]); }
  }
  while (stack.length) {                 // flood inwards from every border O
    const [r, c] = stack.pop();
    for (const [a, b] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
      if (a >= 0 && b >= 0 && a < rows && b < cols && board[a][b] === 'O' && !safe[a][b]) {
        safe[a][b] = true;
        stack.push([a, b]);
      }
    }
  }
  return board.map((row, r) => [...row].map((x, c) => (x === 'O' && !safe[r][c] ? 'X' : x)).join(''));
}

fn solve(board: &[&str]) -> Vec<String> {
    let mut g: Vec<Vec<u8>> = board.iter().map(|row| row.as_bytes().to_vec()).collect();
    let (rows, cols) = (g.len(), g[0].len());
    let mut safe = vec![vec![false; cols]; rows];
    let mut stack = Vec::new();
    for r in 0..rows {
        for c in 0..cols {
            let border = r == 0 || c == 0 || r == rows - 1 || c == cols - 1;
            if border && g[r][c] == b'O' {
                safe[r][c] = true;
                stack.push((r, c));
            }
        }
    }
    while let Some((r, c)) = stack.pop() {      // flood inwards from every border O
        let around = [(r + 1, c), (r.wrapping_sub(1), c), (r, c + 1), (r, c.wrapping_sub(1))];
        for (a, b) in around {
            if a < rows && b < cols && g[a][b] == b'O' && !safe[a][b] {
                safe[a][b] = true;
                stack.push((a, b));
            }
        }
    }
    for r in 0..rows {
        for c in 0..cols {
            if g[r][c] == b'O' && !safe[r][c] {
                g[r][c] = b'X';
            }
        }
    }
    g.into_iter().map(|row| String::from_utf8(row).unwrap()).collect()
}

import qualified Data.Set as S

solve :: [String] -> [String]
solve board = [[cell r c x | (c, x) <- zip [0 ..] row] | (r, row) <- zip [0 ..] board]
  where
    rows = length board
    cols = length (head board)
    os = S.fromList [(r, c) | (r, row) <- zip [0 ..] board, (c, 'O') <- zip [0 ..] row]
    border (r, c) = r == 0 || c == 0 || r == rows - 1 || c == cols - 1
    starts = filter border (S.toList os)
    -- flood inwards from every border O; the set returned is every safe cell
    safe = go starts (S.fromList starts)
    go [] seen = seen
    go ((r, c) : rest) seen =
      let next = [p | p <- [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)], S.member p os, not (S.member p seen)]
      in go (next ++ rest) (foldr S.insert seen next)
    cell r c x
      | x == 'O' && not (S.member (r, c) safe) = 'X'
      | otherwise = x