130. Surrounded Regions
1. Description
Given an m x n matrix board containing ‘X’ and ‘O’, capture all regions that are 4-directionally surrounded by ‘X’.
A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.
2. Example
Example 1:
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”]]
Explanation: Notice that an ‘O’ should not be flipped if:
- It is on the border, or
- It is adjacent to an ‘O’ that should not be flipped.
The bottom ‘O’ is on the border, so it is not flipped.
The other three ‘O’ form a surrounded region, so they are flipped.
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
Time complexity: O(mn)
Space complexity: O(mn)
class Solution {
public:
void solve(vector<vector<char>> &m_board) {
for (int i = 0; i < m_board.size(); ++i) {
if (m_board[i][0] == 'O') {
_mark_connected_o(m_board, i, 0);
}
if (m_board[i][m_board[0].size() - 1] == 'O') {
_mark_connected_o(m_board, i, m_board[0].size() - 1);
}
}
for (int i = 0; i < m_board[0].size(); ++i) {
if (m_board[0][i] == 'O') {
_mark_connected_o(m_board, 0, i);
}
if (m_board[m_board.size() - 1][i] == 'O') {
_mark_connected_o(m_board, m_board.size() - 1, i);
}
}
for (int i = 0; i < m_board.size(); ++i) {
for (int j = 0; j < m_board[0].size(); ++j) {
if (m_board[i][j] == 'O') {
m_board[i][j] = 'X';
} else if (m_board[i][j] == to_o) {
m_board[i][j] = 'O';
}
}
}
}
private:
const char to_o = 'B';
void _mark_connected_o(vector<vector<char>> &m_board, int row, int column) {
if (0 <= row && row < m_board.size() && 0 <= column && column < m_board[0].size() &&
m_board[row][column] == 'O') {
m_board[row][column] = to_o;
_mark_connected_o(m_board, row + 1, column);
_mark_connected_o(m_board, row - 1, column);
_mark_connected_o(m_board, row, column + 1);
_mark_connected_o(m_board, row, column - 1);
}
}
};