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_safe(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                mark_safe(board, i, n - 1);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (board[0][i] == 'O') {
                mark_safe(board, 0, i);
            }
            if (board[m - 1][i] == 'O') {
                mark_safe(board, m - 1, i);
            }
        }

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

private:
    void mark_safe(vector<vector<char>> &board, int i, int j) {
        const int m = board.size(), n = board.front().size();
        if (0 <= i && i < m && 0 <= j && j < n && board[i][j] == 'O') {
            board[i][j] = '#';

            mark_safe(board, i + 1, j);
            mark_safe(board, i - 1, j);
            mark_safe(board, i, j + 1);
            mark_safe(board, i, j - 1);
        }
    }
};