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.
For example,
X X X X X O O X X X O X X O X X
After running your function, the board should be:
X X X X X X X X X X X X X O X XAnswer:
Similar to "Blood Fill" method used in computer game and graphics.
1. DFS (Recursion method), can pass small data set, but time exceeded for large set:
1.1 Directly find 'O', reverse into 'X', then DFS, if there exists an 'O' in corner in this DFS process, then backtrack to 'O'.
class Solution {
public:
void solve(vector<vector<char>> &board) {
if(!board.size())return;
int m= board.size();
int n= board[0].size();
for(int i=0; i<m; ++i){
for(int j= 0; j<n; ++j){
if(board[i][j]=='O'){
DFS(i,j,board);
}
}
}
return;
}
bool DFS(int i, int j,vector<vector<char>> &board){
int m= board.size();
int n= board[0].size();
if(i-1<0 || j-1<0 || i+1>m-1 || j+1>n-1) return false; //corner case: 'O'
board[i][j]= 'X';
if(i-1>=0 && board[i-1][j]=='O'){
if(!DFS(i-1,j,board)){
board[i-1][j]= 'O'; //Backtrack!!!
return false;
}
}
if(j-1>=0 && board[i][j-1]=='O'){
if(!DFS(i,j-1,board)){
board[i][j]= 'O';
return false;
}
}
if(i+1<=m-1 && board[i+1][j]=='O'){
if(!DFS(i+1,j,board)){
board[i][j]= 'O';
return false;
}
}
if(j+1<=n-1 && board[i][j+1]=='O'){
if(!DFS(i,j+1,board)){
board[i][j]= 'O';
return false;
}
}
return true;
}
};
1.2 Find 'O' in the edge firstly, then DFS these "invalid" 'O's, mark them as 'C'. Finally reverse all 'O' into 'X', 'C' into 'O'.
class Solution {
public:
void solve(vector<vector<char>> &board) {
if(!board.size())return;
int m= board.size();
int n= board[0].size();
for(int i=0; i<m; ++i){
if(board[i][0]=='O')
DFS(i,0,board);
if(board[i][n-1]=='O')
DFS(i,n-1,board);
}
for(int i=0; i<n; ++i){
if(board[0][i]=='O')
DFS(0,i,board);
if(board[m-1][i]=='O')
DFS(m-1,i,board);
}
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]=='C')
board[i][j]= 'O';
}
}
return;
}
void DFS(int i, int j,vector<vector<char>> &board){ //Mark all corner 'O' into 'C'.
int m= board.size();
int n= board[0].size();
board[i][j]= 'C';
if(i-1>=0 && board[i-1][j]=='O')
DFS(i-1,j,board);
if(j-1>=0 && board[i][j-1]=='O')
DFS(i,j-1,board);
if(i+1<=m-1 && board[i+1][j]=='O')
DFS(i+1,j,board);
if(j+1<=n-1 && board[i][j+1]=='O')
DFS(i,j+1,board);
return;
}
};
2. BFS: Using queue, iterative, no recursion, can pass large set.
class Solution {
struct pair{
int x,y;
pair(int i,int j):x(i),y(j){};
};
public:
void solve(vector<vector<char>> &board) {
if(!board.size())return;
int m= board.size();
int n= board[0].size();
for(int i=0; i<m; ++i){ //For 'O' in edge case.
if(board[i][0]=='O'){
BFS(i,0,board);
}
if(board[i][n-1]=='O'){
BFS(i,n-1,board);
}
}
for(int i=0; i<n; ++i){
if(board[0][i]=='O'){
BFS(0,i,board);
}
if(board[m-1][i]=='O'){
BFS(m-1,i,board);
}
}
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(board[i][j]=='O') //which 'O' should be flipped to 'X'.
board[i][j]= 'X';
else if(board[i][j]=='C') //which 'O' shouldn't be flipped.
board[i][j]= 'O';
}
}
return;
}
void BFS(int a,int b,vector<vector<char>> &board){ //Mark all corner 'O' into 'C'.
int m= board.size();
int n= board[0].size();
queue<pair> que;
board[a][b]= 'C';
que.push(pair(a,b));
while(!que.empty()){
pair t= que.front();
que.pop();
int i= t.x;
int j= t.y;
if(i-1>=0 && board[i-1][j]=='O'){
board[i-1][j]= 'C';
que.push(pair(i-1,j));
}
if(j-1>=0 && board[i][j-1]=='O'){
board[i][j-1]= 'C';
que.push(pair(i,j-1));
}
if(i+1<=m-1 && board[i+1][j]=='O'){
board[i+1][j]= 'C';
que.push(pair(i+1,j));
}
if(j+1<=n-1 && board[i][j+1]=='O'){
board[i][j+1]= 'C';
que.push(pair(i,j+1));
}
}
return;
}
};
No comments:
Post a Comment