BFS solution with 2 queues


#1

Blockquote
void Solution::solve(vector<vector > &A) {
queue <pair<int ,int >> q;
queue <pair<int ,int >> q2;
for(int i=0;i<A.size();i++){
if(A[i][0]==‘O’) q.push(make_pair(i,0));
f(A[i][A[0].size()-1]==‘O’) q.push(make_pair(i,A[0].size()-1));
}
for(int i=0;i<A[0].size();i++){
if(A[0][i]==‘O’) q.push(make_pair(0,i));
if(A[A.size()-1][i]==‘O’) q.push(make_pair(A.size()-1,i));
}
int visited[A.size()][A[0].size()]={0};
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
if( x+1<A.size() &&y<A[0].size() && x>=0&&y>=0&&A[x+1][y]==‘O’&&visited[x+1][y]==0) q.push(make_pair(x+1,y));
if( x<A.size() &&y+1<A[0].size()&& x>=0&&y>=0&&A[x][y+1]==‘O’&&visited[x][y+1]==0) q.push(make_pair(x,y+1));
if( x<A.size() && y<A[0].size()&&x-1>=0&&y>=0&&A[x-1][y]==‘O’&&visited[x-1][y]==0) q.push(make_pair(x-1,y));
if( x<A.size() && y<A[0].size()&&x>=0&&y-1>=0&&A[x][y-1]==‘O’&&visited[x][y-1]==0) q.push(make_pair(x,y-1));
visited[x][y]=1;
q2.push(q.front());

q.pop();
}

for(int i=0;i<A.size();i++){
 for(int j=0;j<A[0].size();j++){
    A[i][j]='X';
 }   
}

while(!q2.empty()){
int x=q2.front().first;
int y=q2.front().second;
    A[x][y]='O';
    q2.pop();
    
}

}