Surrounded Regions

这个问题有那么点感觉，但是就是不对路，开始想的是从左上角到右下角，若其左和上都是‘X‘就将其改为’X‘，然后再从右下往上反，将“误杀”的还原回来，当然这要借助复制的一份board，但最终结果还是不对，因为有出现“弯路”的时候就不行了，后来想着再从右上到左下也如此操作一番，最终是没能得逞。几天无果，看了下discuss区，顿感醍醐灌顶，再看这个题，就 是呵呵。

思路是从外围是’O‘的开始深度往里走，这时候里面的‘O‘就有两种命运，一种是跟外围的’O‘是联通的，那么这些‘O‘就可以存活，剩下的孤立的’O‘就没办法了，就只能被‘X‘了，为了区分这两种’O‘，我们把联通 的‘O‘改为另外一种统一而独立的字符，便于后期做恢复。这就是三步走（或两步）。

1）首先从外围的‘O‘处深度搜索，见到链接的’O‘就把他们都改为其他标识。

2）将剩余的孤立的’O‘改为‘X‘，同时，将遇到标识符改为’O‘。

简单吧，简单的一塌糊涂，但是这种思路太精髓了。

详细参考见：http://discuss.leetcode.com/questions/1223/surrounded-regions

                                http://blog.sina.com.cn/s/blog_b9285de20101j1dt.html

class Solution {
private:
	int rows;
	int cols;
public:
	void dfs(int row, int col,vector<vector<char> >& board)
	{
		if(row < 0 || row >= rows || col < 0 || col >= cols) return;
		if(board[row][col] != ‘O‘) return;
		board[row][col] = ‘+‘;
		dfs(row - 1, col, board);//up
		dfs(row, col + 1, board);//right
		dfs(row + 1, col, board);//down
		dfs(row, col - 1, board);//left
	}
	void solve(vector<vector<char> > &board)
	{
		if(board.size() == 0 || board[0].size() == 0)
			return;
		 rows = board.size();
		 cols = board[0].size();
		 for(int i = 0; i < rows; ++i){
			 dfs(i, 0, board);
			 dfs(i, cols - 1, board);
		 }
		 for (int j = 0; j < cols; ++j)
		 {
			 dfs(0, j, board);
			 dfs(rows - 1, j, board);
		 }
		 for(int i = 0; i < rows; ++i)
			 for (int j = 0; j < cols; ++j)
			 {
				if(board[i][j] == ‘O‘)
					board[i][j] = ‘X‘;
				else if(board[i][j] == ‘+‘)
					 board[i][j] = ‘O‘;		 
			 }	 
	}
};

Surrounded Regions

原文：http://blog.csdn.net/shiquxinkong/article/details/18241833