LeetCode June Challenge - Day 17

Problem: LeetCode June Challenge - Day 17

Ideas:

1. A region is not surrounded if some element is in the border.
2. A region is a connected component in an undirected graph.
3. You only need to check the ‘O’ in the borders and find it’s connected components. Here are some details of my implementation:
• I use the board as a visited array, flipping ‘O’ to ‘1’.
• After this, the board has ‘1’ where there should be ‘O’, and ‘O’ where there should be ‘X’. Just flip these values.

Solution:

``````class Solution {
int n, m;

void dfs(int i, int j, vector<vector<char>>& b){
b[i][j] = '1';
if(i < n-1 && b[i+1][j] == 'O') dfs(i+1, j, b);
if(i > 0 && b[i-1][j] == 'O') dfs(i-1, j, b);
if(j < m-1 && b[i][j+1] == 'O') dfs(i, j+1, b);
if(j > 0 && b[i][j-1] == 'O') dfs(i, j-1, b);
}

public:
void solve(vector<vector<char>>& board) {
n = board.size();
if(n == 0) return;
m = board[0].size();

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

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