# Untitled

unknown
plain_text
a year ago
2.4 kB
1
Indexable
Never
```class Solution { //ANY REGIONS NOT CONNECTED TO THE BORDER WILL BE FLOODED
public:
void dfs(vector<vector<char>>& board,int x,int y){
if(x<0 || x>=board.size() || y<0 || y>=board[0].size() || board[x][y]!='O') return;
board[x][y]='T';
dfs(board,x-1,y);
dfs(board,x+1,y);
dfs(board,x,y-1);
dfs(board,x,y+1);
}

void solve(vector<vector<char>>& board) {
int r=board.size(), c=board[0].size();
for(int i=0;i<r;i++){
if(board[i][c-1]=='O') dfs(board,i,c-1);
if(board[i][0]=='O') dfs(board,i,0);
}

for(int i=0;i<c;i++){
if(board[0][i]=='O') dfs(board,0,i);
if(board[r-1][i]=='O') dfs(board,r-1,i);
}
//every safe has been marked , now mark erevything else as X
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(board[i][j]=='O') board[i][j]='X';
}
}
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(board[i][j]=='T') board[i][j]='O';
}
}

}
};

/***************************************************************

class Solution { //WRONG APPROACH
public:
bool up(vector<vector<char>>& board,int x,int y){ //returns true if surrounded by X on up
while(x>=0){
if(board[x][y]=='X') {
return true;
}
x--;
}
return false;
}

bool down(vector<vector<char>>& board,int x,int y){
int r=board.size();
while(x<r){
if(board[x][y]=='X') return true;
x++;
}
return false;
}

bool left(vector<vector<char>>& board,int x,int y){
while(y>=0){
if(board[x][y]=='X') return true;
y--;
}
return false;
}
bool right(vector<vector<char>>& board,int x,int y){
int c=board[0].size();
while(y<c){
if(board[x][y]=='X') return true;
y++;
}
return false;
}

void solve(vector<vector<char>>& board) {
int r=board.size();
int c=board[0].size();
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(board[i][j]=='O' && left(board,i,j) && right(board,i,j) && up(board,i,j) && down(board,i,j)) board[i][j]='X';
}
}
}
}; */```