[leetcode] 130 Surrounded Regions (done)

/*
http://leetcode.com/onlinejudge#question_130

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

*/

class Solution {
public:
    typedef vector<char> row_t;
    typedef vector<row_t> board_t;

    void bfs_replace(board_t & board, int r, int c,
        char replacee, char replacer)
    {
        const int R = board.size();
        const int C = board[0].size();

        typedef pair<int, int> intpair;
        deque<intpair> Q;

        Q.push_back(make_pair(r,c));
        while(!Q.empty())
        {
            intpair rc = Q.front();
            Q.pop_front();

            r = rc.first;
            c = rc.second;

            if(r < 0 || r >= R || c < 0 || c >= C) { continue; }
            if(board[r][c] != replacee) { continue; }
            board[r][c] = replacer;

            Q.push_back(make_pair(r-1, c));
            Q.push_back(make_pair(r+1, c));
            Q.push_back(make_pair(r, c-1));
            Q.push_back(make_pair(r, c+1));
        }
    }
    void replace_all(board_t & board, char replacee, char replacer)
    {
        const int R = board.size();
        const int C = board[0].size();

        for(int r = 0; r < R; ++r)
        {
            for(int c = 0; c < C; ++c)
            {
                if(board[r][c] == replacee)
                {
                    board[r][c] = replacer;
                }
            }
        }
    }


    void solve(board_t &board) {

        if(board.empty()) { return; }

        const int R = board.size();
        const int C = board[0].size();

        const char replacee = 'O';
        const char mark = 'V';

        // mark all 'O' that touch border and their
        // neighbours with mark 'V'
        for(int r = 0; r < R; ++r)
        {
            if(board[r][0] == replacee)
            {
                bfs_replace(board, r, 0, replacee, mark);
            }
            if(board[r][C-1] == replacee)
            {
                bfs_replace(board, r, C-1, replacee, mark);
            }
        }
        for(int c = 0; c < C; ++c)
        {
            if(board[0][c] == replacee)
            {
                bfs_replace(board, 0, c, replacee, mark);
            }
            if(board[R-1][c] == replacee)
            {
                bfs_replace(board, R-1, c, replacee, mark);
            }
        }
        // replace all remaining 'O' with 'X'
        replace_all(board, replacee, 'X');

        // replace all 'V' back to 'O'
        replace_all(board, mark, replacee);
    }
};