学步园

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

还是老毛病啊，整体思路一下就有了，但是写出来的代码总不能一下就过。

其实前一阵面微软的时候二面考的算法就跟这个有相似的地方，总的来说都可以归结为一个连通性的问题，用BFS；

1.很明显在最外面一圈的O挨着的O肯定最后不是被包围的，与这个O也相连的也不能被包围，即这些O在最后的矩阵里面还是O；

2.我们从最外面一圈的O出发，用BFS，利用队列帮助进行扩展，将所有它能联通到的O都标记，

3.随后我们再扫描一遍矩阵，被标记的改回O,没有被标记的O都是可以被包围的，所以要改成X；

代码：

上次面微软现场写代码，有一段跟下面　//extending  那里一样，要从四个方向扩展，然后面试官就很不满意，说你这个那不得写四次，我说要扩展四个方向，所以是要写四次，结果他非常不满，说这样的代码非常不整洁，有方法可以改的，然后我问他怎么写他又不说，各位有知道的吗，烦请告知，或者有那本书推荐的吗？

class Solution {
public:
    void process(int i,int j,vector<vector<char> >& board)
	{
		int m=board.size();
		int n=board[0].size();

		typedef pair<int,int> point;
		queue<point> Q;
		Q.push(point(i,j));
		board[i][j]='E';
		while(!Q.empty())
		{
			point tmp=Q.front();
			Q.pop();
			
			int x=tmp.first,y=tmp.second;

			//extending
			if (x!=0&&board[x-1][y]=='O')
			{
				Q.push(point(x-1,y));
				board[x-1][y]='E';   //extended;
			}
			if (x!=m-1&&board[x+1][y]=='O')
			{
				Q.push(point(x+1,y));
				board[x+1][y]='E';   //extended;
			}
			if (y!=0&&board[x][y-1]=='O')
			{
				Q.push(point(x,y-1));
				board[x][y-1]='E';   //extended;
			}
			if (y!=n-1&&board[x][y+1]=='O')
			{
				Q.push(point(x,y+1));
				board[x][y+1]='E';   //extended;
			}
		}
	}
	void solve(vector<vector<char> >& board)
	{
		int m=board.size();
		if (m==0)
			return;
		int n=board[0].size();
		int i,j;
		for(i=0;i<m;i++)
		{
			if (board[i][0]=='O')
				process(i,0,board);
			if (board[i][n-1]=='O')
				process(i,n-1,board);
		}
		for(j=0;j<n;j++)
		{
			if (board[0][j]=='O')
				process(0,j,board);
			if (board[m-1][j]=='O')
				process(m-1,j,board);
		}
		for(i=0;i<m;i++)
			for(j=0;j<n;j++)
			{
				if(board[i][j]=='O')
					board[i][j]='X';
				else if (board[i][j]=='E')
					board[i][j]='O';
			}
	}	
};