CaptureRegion-Interviewbit.cpp

Capture Regions on Board

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X


void Traverse(vector<vector<char> > &A, int i, int j, bool &flag)
{
    int m = A.size();
    int n = A[0].size();
    
    if(i == 0 || j == 0 || i == (m-1) || j == (n-1) )
    {
        flag = true;
    }
    
    A[i][j] = 'V';
    
    if(i > 0 && A[i-1][j] == 'O')
    {
        Traverse(A,i-1,j,flag);
    }
    
    if(j > 0 && A[i][j-1] == 'O')
    {
        Traverse(A,i,j-1,flag);
    }
    
    if(i < (m-1) && A[i+1][j] == 'O')
    {
        Traverse(A,i+1,j,flag);
    }
    
    if(j < (n-1) && A[i][j+1] == 'O')
    {
         Traverse(A,i,j+1,flag);
    }
}

void Mark(vector<vector<char> > &A, int i, int j)
{
    int m = A.size();
    int n = A[0].size();
    
    A[i][j] = 'X';
    
    if(i > 0 && A[i-1][j] == 'V')
    {
        Mark(A,i-1,j);
    }
    
    if(j > 0 && A[i][j-1] == 'V')
    {
        Mark(A,i,j-1);
    }
    
    if(i < (m-1) && A[i+1][j] == 'V')
    {
        Mark(A,i+1,j);
    }
    
    if(j < (n-1) && A[i][j+1] == 'V')
    {
         Mark(A,i,j+1);
    }
}
void Solution::solve(vector<vector<char> > &A) {
   
   int m = A.size();
   int n = A[0].size();
   
   for(int i = 0; i < m; i++)
   {
       for(int j = 0; j < n; j++)
       {
           if(A[i][j] == 'O')
           {
               bool flag = false;
               Traverse(A,i,j,flag);
               if(flag == false)
               {
                   Mark(A,i,j);
               }
           }
       }
   }
   
   for(int i = 0; i < m; i++)
   {
       for(int j = 0; j < n; j++)
       {
           if(A[i][j] == 'V')
           {
               A[i][j] = 'O';
           }
       }
   }
}