130. Surrounded Regions

2024, Apr 16 2 mins read

1. Description

You are given an m x n matrix board containing letters ‘X’ and ‘O’, capture regions that are surrounded:

Connect: A cell is connected to adjacent cells horizontally or vertically.
Region: To form a region connect every ‘O’ cell.
Surround: A region is surrounded if none of the ‘O’ cells in that region are on the edge of the board. Such regions are completely enclosed by ‘X’ cells.

To capture a surrounded region, replace all ‘O’s with ‘X’s in-place within the original board. You do not need to return anything.

2. Example

Example 1

Leetcode 130
Input: board = [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”]]
Output: [[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“O”,“X”,“X”]]
In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

Example 2

Input: board = [[“X”]]
Output: [[“X”]]

3. Constraints

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is ‘X’ or ‘O’.

4. Solutions

Depth-First Search

m = board.size(), n = board.front().size()
Time complexity: O(mn)
Space complexity: O(mn)

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        const int m = board.size(), n = board.front().size();
        for (int i = 0; i < m; ++i) {
            if (board[i][0] == 'O') {
                mark_alive_region(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                mark_alive_region(board, i, n - 1);
            }
        }

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

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

private:
    const array<pair<int, int>, 4> directions = {{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}};
    void mark_alive_region(vector<vector<char>> &board, int row, int column) {
        const int m = board.size(), n = board.front().size();

        board[row][column] = 'U';
        for (auto dir : directions) {
            int next_row = row + dir.first, next_column = column + dir.second;
            if (0 <= next_row && next_row < m && 0 <= next_column && next_column < n &&
                board[next_row][next_column] == 'O') {
                mark_alive_region(board, next_row, next_column);
            }
        }
    }
};