Capture Regions C++ BFS solution


#1
vector<pair<int,int>> add_neighbors(int i, int j, vector<vector<char> > &A,map<pair<int,int>,int> &m){

int r=A.size();
int c=A[0].size();

vector<pair<int,int>> neighbors;

int x[]={-1,1,0,0};
int y[]={0,0,-1,1};    
for(int t=0;t<4;t++){
    if(i+x[t]<r and i+x[t]>=0 and j+y[t]<c and j+y[t]>=0 and A[i+x[t]][j+y[t]]=='O' 
        and m.find(make_pair(i+x[t],j+y[t]))==m.end())
        neighbors.push_back(make_pair(i+x[t],j+y[t]));
}
return neighbors;

}

void bft(int x, int y, vector<vector > &A, map<pair<int,int>,int> &m){

queue<pair<int,int>> q;
q.push(make_pair(x,y));
m[make_pair(x,y)]=1;

while(!q.empty()){
    pair<int,int> front = q.front();
    q.pop();
    int i=front.first,j=front.second;
    vector<pair<int,int>> neighbors = add_neighbors(i,j,A,m);
    
    for(int t=0;t<neighbors.size();t++){
        int ni=neighbors[t].first, nj = neighbors[t].second;
        m[make_pair(ni,nj)]=1;
        q.push(make_pair(ni,nj));
    }
}

}

void Solution::solve(vector<vector > &A) {

if(A.size()<=1 or A[0].size()<=1)
    return;

int r=A.size();
int c = A[0].size();

map<pair<int,int>,int> m;

for(int i=0;i<r;i+=r-1){
    for(int j=0;j<c;j++){
        if(A[i][j]=='O'){
            bft(i,j,A,m);
        }
    }
}

 for(int j=0;j<c;j+=c-1){
    for(int i=0;i<r;i++){
        if(A[i][j]=='O'){
            bft(i,j,A,m);
        }
    }
}   

for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
        if(A[i][j]=='O' and m.find(make_pair(i,j))==m.end())
            A[i][j]='X';
    }
}

}