Using BFS traversal


#1
int X[]={-1,-1,-1,0,0,1,1,1};
int Y[]={1,0,-1,1,-1,1,0,-1};
int n,m;

bool isValid(int x,int y)
{
    if(x<0 || x>=n || y<0 || y>=m)
    {
        return false;
    }
    return true;
}
void bfs(int i,int j, vector<vector<char> > &Vec)
{
    queue<pair<int, int> > Que;
    Que.push(make_pair(i, j));

    while(!Que.empty()) 
    {
        pair<int, int> P = Que.front();
        Que.pop();
        Vec[P.first][P.second] = 'M';
        for(int k = 0; k < 8; ++k) 
        {
            int x = P.first + X[k];
            int y = P.second + Y[k];
            if(isValid(x, y) && Vec[x][y] == 'O') 
            {
                Que.push(make_pair(x, y));
            }
        }
    }    
}

void Solution::solve(vector<vector<char> > &A) 
{
    n=A.size();
    m=A[0].size();
    for(int i=0;i<n;i++)
    {   int j=0;
        if(A[i][j]=='O')
        {
            bfs(i,j,A);
        }
    }
    for(int i=0;i<m;i++)
    {   int j=0;
        if(A[j][i]=='O')
        {
            bfs(j,i,A);
        }
    }
    for(int i=0;i<m;i++)
    {   int j=n-1;
        if(A[j][i]=='O')
        {
            bfs(j,i,A);
        }
    }
    for(int i=0;i<n;i++)
    {   int j=m-1;
        if(A[i][j]=='O')
        {
            bfs(i,j,A);
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(A[i][j]!='M')
            {
                A[i][j]='X';
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(A[i][j]=='M')
            {
                A[i][j]='O';
            }
        }
    }
    
}

#2

failed for
[ “XOXXXXOOXX”, “XOOOOXOOXX”, “OXXOOXXXOO”, “OXOXOOOXXO”, “OXOOXXOOXX”, “OXXXOXXOXO”, “OOXXXXOXOO” ]