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'; } } } }; */