Tuesday, December 2, 2014

Surrounded Regions

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

Idea:
Use BFS

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        int row = board.size();
        if (row<=1) return;
        int col = board[0].size();
        if (col<=1) return;
        for (int c=0; c<col; c=c+col-1)
        for (int r=0; r<row; r++)
         {
             if (board[r][c]=='O')
                findBdCoords(board,r, c, row, col);
         }
       
        for (int r=0; r<row; r=r+row-1)
        for (int c=0; c<col; c++)
        {
             if (board[r][c]=='O')
                findBdCoords(board,r, c, row, col);           
        }
        for (int r=0; r<row; r++)
        for (int c=0; c<col; c++)
        {
             if (board[r][c]=='O')
                   board[r][c]='X';
             if (board[r][c]=='B')
                 board[r][c]='O';
        }      
    }
    void findBdCoords(vector<vector<char>> &board, int r, int c, int row, int col)
    {
        if (board[r][c]!='B')
            board[r][c]='B';
        queue<pair<int,int>> q;
        q.push(make_pair(r,c));
       
        while(!q.empty())
        {
           //4 directions neighbor
           pair<int,int> cur = q.front();
           q.pop();
          
           r = cur.first, c = cur.second;
           pair<int, int> neis[4]={{r+1,c},{r-1,c},{r,c+1},{r,c-1}};
          
           for (int i=0; i<4; i++)
           {
               int rt = neis[i].first, ct = neis[i].second;
               if (rt>=0&&ct>=0&&rt<row&&ct<col&&board[rt][ct]=='O')
               {
                   q.push(make_pair(rt,ct));     
                    board[rt][ct]='B';               
               }
           }
        }
    }
};

No comments:

Post a Comment