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

Solution:

Basic idea is that, since only nodes that connected to the boundary can survive, how about we start from the boundary nodes and go inside, i.e., do BFS for all 4 boundary nodes. Mark the survive node as *, after every boundary nodes have been checked. Change x and o to x, and * to o.

To save space, mark the survive node as *, or we can use a set to remember the index, but that will use O(MN) space, the * method need one extra swipe of all the nodes after the algorithm.

Use Queue for BFS.
First run didn't pass the time limit, even if I use queue for BFS. Because I put the position into queue, then when pop, to set the element to '*'. This leaves a lot of repeated position element in queue.
*****
Set element to '*' before put it into queue.

Code:
void solve(vector > &board) {
    int m=board.size();
    int n;
    if (m) n=board[0].size();

     if (m<3 n="" p="" return="">
     queue< pair > que;

    for(int i=0; i    {
        if (board[0][i]=='O')
        {
            board[0][i]='*';
            que.push( pair(0,i) );
            bfs(que, board, m, n);
        }

        if (board[m-1][i]=='O')
        {
            board[m-1][i]='*';
            que.push( pair(m-1,i) );
        bfs (que, board, m, n);
        }
    }

    for(int i=0; i    {
        if (board[i][0]=='O')
        {
            board[i][0]='*';
            que.push( pair(i,0) );
        bfs(que, board, m, n);
        }

        if (board[i][n-1]=='O')
        {
            board[i][n-1]='*';
            que.push( pair(i,n-1) );
            bfs (que, board, m, n);
        }
    }

    for(int i=0; i    {
        for(int j=0; j        {
            if(board[i][j]=='*')
                board[i][j]='O';
            else
                board[i][j]='X';
        }
    }

   return;
}

void bfs(queue> &que, vector > &board, int m, int n)
{
    while(!que.empty())
    {
        pair aa = que.front();
        que.pop();
        int x = aa.first;
        int y = aa.second;

        if (x-1>=0 && x-1(x-1,y) ); }
        if (x+1>=0 && x+1(x+1,y) ); }
        if (y-1>=0 && y-1(x,y-1) ); }
        if (y+1>=0 && y+1(x,y+1) ); }
    }
    return;
}