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

这道题很好体现基本搜索算法。两种经典算法深度优先、广度优先。

在实现深度优先时我尝试使用java实现，发现无法AC，会出现栈溢出错误，但是通过使用c++引用时间却少很多。

未AC的java代码：

public class Solution {
    	public void solve(char[][] board) {
		if(board.length ==0 || board[0].length == 0){
			return;
		}			
		int rows = board.length;
		int cols = board[0].length;
		for(int i=0;i
  
   =rows || row<0 || col>=cols || col<0){
			return;
		}
		if(board[row][col]!='O'){
			return;
		}
		board[row][col] = '+';
		dfs(board, row-1, col);// up
		dfs(board, row+1, col);// down
		dfs(board, row, col-1);// left
		dfs(board, row, col+1);// right
	}
}
  

DFS 深度优先：C++实现不会出现超时问题

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

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

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

已经AC的C++代码。

class Solution {
private:
	int rows;
	int cols;
public:
	void dfs(int row, int col,vector
  
    >& 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
   
     > &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'; } } };
   
  

其实这里使用广度优先搜索可能更好理解，下面使用java 进行广度优先搜索实现：

已经AC的java广搜代码。

public class Solution {
	int m, n;
	char[][] board;
	boolean [][] flag;
	Queue
  
    queue = new LinkedList
   
    (); public void solve(char[][] board) { if (board == null || board.length == 0) return; flag = new boolean[board.length][board[0].length];// 标记位置是否来过 this.board = board; m = board.length; n = board[0].length; for (int j = 0; j < n; j++) { bfs(0, j); bfs(m - 1, j); } for (int i = 0; i < m ; i++) { bfs(i, 0); bfs(i, n - 1); } for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { if (board[i][j] == 'O') board[i][j] = 'X'; else if (board[i][j] == 'D') board[i][j] = 'O'; } } void fill(int x, int y) { if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O' || flag[x][y] == true) return; flag[x][y] = true; queue.offer(x * n + y); board[x][y] = 'D'; } public void bfs(int x, int y) { fill(x, y); while (!queue.isEmpty()) { int curr = queue.poll(); int i = curr / n; int j = curr % n; fill(i - 1, j); fill(i + 1, j); fill(i, j - 1); fill(i, j + 1); } } }