Given a 2D board containing'X'
and'O'
, capture all regions surrounded by'X'
.
A region is captured by flipping all'O'
's into'X'
's in that surrounded region.
Have you met this question in a real interview?
Yes
Example
X X X X
X O O X
X X O X
X O X X
After capture all regions surrounded by'X'
, the board should be:
X X X X
X X X X
X X X X
X O X X
column size
check each line right away after writing down
class Solution {
public:
/\*\*
\* @param board a 2D board containing 'X' and 'O'
\* @return void
\*/
void surroundedRegions\(vector<vector<char>>& board\) {
// Write your code here
if \(board.empty\(\) \|\| board\[0\].empty\(\)\) {
return;
}
int n = board.size\(\);
int m = board\[0\].size\(\);
//cout << n << " " << m << endl;
parent.resize\(n\*m+1\);
std::iota\(parent.begin\(\), parent.end\(\), 0\);
int dummy = n\*m;
vector<vector<int>> dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
for \(int i = 0; i < n; ++i\) {
for \(int j = 0; j < m; ++j\) {
if \(board\[i\]\[j\] == 'O'\) {
if \(isOnBorder\(i, j, n, m\)\) {
Union\(convertToId\(i, j, m\), dummy\);
} else {
for \(auto dir : dirs\) {
int ni = i + dir\[0\];
int nj = j + dir\[1\];
if \(isInside\(ni, nj, n, m\) && board\[ni\]\[nj\] == 'O'\) {
Union\(convertToId\(i, j, m\), convertToId\(ni, nj, m\)\);
}
}
}
}
}
}
for \(int i = 0; i < n; ++i\) {
for \(int j = 0; j < m; ++j\) {
if \(board\[i\]\[j\] == 'O' && cfind\(convertToId\(i, j, m\)\) != cfind\(dummy\)\) {
board\[i\]\[j\] = 'X';
}
}
}
}
private:
bool isOnBorder\(int i, int j, int n, int m\) {
return \(i == 0\) \|\| \(i == n-1\) \|\| \(j == 0\) \|\| \(j == m-1\);
}
bool isInside\(int i, int j, int n, int m\) {
return \(i >= 0\) && \(i < n\) && \(j >= 0\) && \(j < m\);
}
int convertToId\(int i, int j, int m\) {
return i\*m + j;
}
vector<int> parent;
int cfind\(int i\) {
int fa = i;
while \(parent\[fa\] != fa\) {
fa = parent\[fa\];
}
while \(parent\[i\] != i\) {
int temp = parent\[i\];
parent\[i\] = fa;
i = temp;
}
return fa;
}
int find\(int i\) {
while \(parent\[i\] != i\) {
i = parent\[i\];
}
return i;
}
void Union\(int a, int b\) {
int pa = cfind\(a\);
int pb = cfind\(b\);
if \(pa != pb\) {
parent\[pa\] = pb;
}
}
};