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 XX O O XX X O XX O X X

After running your function, the board should be:

X X X XX X X XX X X XX 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<cols;i++){			dfs(board, 0, i);			dfs(board, rows-1, i);		}		for(int i=1;i<rows;i++){			dfs(board, i, 0);			dfs(board, i, cols-1);		}		for(int i=0;i<rows;i++){			for(int j=0;j<cols;j++){				if(board[i][j]== 'O'){					board[i][j] = 'X';				}				if(board[i][j]== '+'){					board[i][j] = 'O';				}			}		}			}	public void dfs(char[][] board,int row,int col){		int rows = board.length;		int cols = board[0].length;		if(row>=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<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';		 			 }	 	}};

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

已经AC的java广搜代码。

public class Solution {	int m, n;	char[][] board;	boolean [][] flag;	Queue<Integer> queue = new LinkedList<Integer>();	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);		}	}}

Surrounded Regions