题目：
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: void solve(vector<vector<char>>& board) { const int ROW = board.size(); if ( ROW<3 ) return; const int COL = board[0].size(); // first row for ( int i = 0; i < COL; ++i ) {if ( board[0][i]=='O') { board[0][i] = 'M'; Solution::bfs(board, 0, i, ROW, COL); }} // last row for ( int i = 0; i < COL; ++i ) {if ( board[ROW-1][i]=='O' ) { board[ROW-1][i] = 'M'; Solution::bfs(board, ROW-1, i, ROW, COL); }} // first col for ( int i = 0; i < ROW; ++i ) {if ( board[i][0]=='O' ) { board[i][0] = 'M'; Solution::bfs(board, i, 0, ROW, COL); }} // last col for ( int i = 0; i < ROW; ++i ) {if ( board[i][COL-1]=='O' ) { board[i][COL-1]='M'; Solution::bfs(board, i, COL-1, ROW, COL); }} // flipping surrounded regions for ( int i = 0; i < ROW; ++i ){ for ( int j = 0; j < COL; ++j ){ if ( board[i][j]=='O' ) { board[i][j]='X'; continue; } if ( board[i][j]=='M' ) { board[i][j]='O'; continue; } } } } static void bfs(vector<vector<char> >& board, int row, int col, int ROW, int COL ) { queue<pair<int, int> > que; que.push(make_pair(row, col)); while ( !que.empty() ){ int r = que.front().first, c = que.front().second; que.pop(); // up left down right if ( r-1>0 && board[r-1][c]=='O' ) { board[r-1][c]='M'; que.push(make_pair(r-1, c)); } if ( c-1>0 && board[r][c-1]=='O') { board[r][c-1]='M'; que.push(make_pair(r, c-1)); } if ( r+1<ROW-1 && board[r+1][c]=='O' ) { board[r+1][c]='M'; que.push(make_pair(r+1, c)); } if ( c+1<COL-1 && board[r][c+1]=='O' ) { board[r][c+1]='M'; que.push(make_pair(r, c+1)); } } } };
tips：
参考的BFS的思路（http://yucoding.blogspot.sg/2013/08/leetcode-question-131-surrounded-regions.html）
先说大体思路
这个思路正好与常规的思路逆过来：
1. 常规的思路是从wall里面挨个BFS遍历，如果从一个'O'出发的所有点都满足封住了，则这BFS走过的点都被封住了，最后赋值为'X'（这样会超时）
2. 而这道题的思路比较好的是逆过来，从边界的'O'出发BFS（因为只要跟边界的'O'连上了，就必然封不住了；而没有与边界的'O'边界连上的'O'自然被封住了）
再说实现细节：
1. 为了不使用额外空间，对于由边界'O'经BFS得到的'O'都置为'M'（M有两个意思：一是访问过了，不用再访问了；二是这个点再最后要恢复为'O'）
2. BFS的时候，终止条件第一次直接写的是que.empty()，一直不对；后来改成了!que.empty()才对，这个低级错误不要再犯。
=========================================
第二次过这道题，有个细节没有注意：
如果发现一个点四周的点是要保留的‘O’时，一定要马上将其设置为‘M’，然后再进行BFS；如果不马上设置为‘M'，那么在BFS的过程中，可能会重复过这个点。
class Solution { public: void solve(vector<vector<char> >& board) { if ( board.size()<3 ) return; const int m = board.size(); const int n = board[0].size(); // search from first row for ( int i=0; i<n; ++i ) { if ( board[0][i]=='O' ) Solution::bfs(board, 0, i, m, n); } // search from last row for ( int i=0; i<n; ++i ) { if ( board[m-1][i]=='O' ) Solution::bfs(board, m-1, i, m, n); } // search from first column for ( int i=0; i<m; ++i ) { if ( board[i][0]=='O' ) Solution::bfs(board, i, 0, m, n); } // search from last column for ( int i=0; i<m; ++i ) { if ( board[i][n-1]=='O' ) Solution::bfs(board, i, n-1, m, n); } // trans 'O' to 'X' & trans 'M' to 'O' for ( int i=0; i<m; ++i ) { for ( int j=0; j<n; ++j ) { if ( board[i][j]=='O' ) { board[i][j]='X'; continue; } if ( board[i][j]=='M' ) { board[i][j]='O'; } } } } static void bfs(vector<vector<char> >& board, int r, int c, int ROW, int COL) { board[r][c] = 'M'; queue<pair<int, int> > curr; queue<pair<int, int> > next; curr.push(make_pair(r, c)); while ( !curr.empty() ) { while ( !curr.empty() ) { int i = curr.front().first; int j = curr.front().second; curr.pop(); // up if ( i-1>=0 && board[i-1][j]=='O' ) { board[i-1][j] = 'M'; next.push(make_pair(i-1, j)); } // down if ( i+1<ROW && board[i+1][j]=='O' ) { board[i+1][j] = 'M'; next.push(make_pair(i+1, j)); } // left if ( j-1>=0 && board[i][j-1]=='O' ) { board[i][j-1] = 'M'; next.push(make_pair(i, j-1)); } // right if ( j+1<COL && board[i][j+1]=='O' ) { board[i][j+1] = 'M'; next.push(make_pair(i, j+1)); } } swap(next, curr); } } };