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 XX O O XX X O XX O X X

 

After running your function, the board should be:

X X X XX X X XX X X XX O X X

class Solution {public:    int dir[4][2] = {
    {0,1},{0,-1},{1,0},{-1,0}};    void solveUtil(vector
     
      
        >& board, vector
       
        
          >& visited, int ix, int iy, vector
         
          
            >& curPath, bool& isSurrounded) { int n = board.size(); int m = board[0].size(); queue
           
            
              > posQ; posQ.push(pair
             
              (ix, iy)); while(!posQ.empty()) { int curX = posQ.front().first; int curY = posQ.front().second; posQ.pop(); if(board[curX][curY] == 'O' && !visited[curX][curY]) { curPath.push_back(pair
              
               (curX, curY)); visited[curX][curY] = true; for(int k = 0; k < 4; ++k) { int newX = curX+dir[k][0]; int newY = curY+dir[k][1]; if(newX < 0 || newX >= n || newY < 0 || newY >= m) isSurrounded = false; else if (!visited[newX][newY]) posQ.push(pair
               
                (newX, newY)); } } } } void solve(vector
                
                 
                  > &board) { // Start typing your C/C++ solution below // DO NOT write int main() function int n = board.size(); if(n == 0) return; int m = board[0].size(); vector
                  
                   
                     > visited(n, vector
                    
                     (m, false)); for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { vector
                     
                      
                        > curPath; bool isSurrounded = true; if(!visited[i][j]) solveUtil(board, visited, i, j, curPath, isSurrounded); if(isSurrounded) { for(int i = 0; i < curPath.size(); ++i) board[curPath[i].first][curPath[i].second] = 'X'; } } } }};