Surrounded Regions
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
这道题要考虑的不是去寻找哪些被X包围，应该考虑从四个边界，找出与O相连的就是没有被包围的。这里用的是BFS从四个边界进行BFS找出与边界O相连的做好标记，这里是将其变成Z。
BFS完成以后这个board 进行遍历，如果是Z则变成O，其余的都变成X
BFS使用一个队列，将其周围满足条件的都加入到队列中，这里不用使用递归
import java.util.LinkedList;
import java.util.Queue; public class Solution {
private char board[][];
private int rows;
private int cols; //行和列数
private Queue<Integer> queue = new LinkedList<Integer>(); //BFS使用的队列 public void solve(char[][] board) {
this.board = board;
if(null == board || board.length == 0 || board[0].length == 0) //特殊的直接返回
return;
rows = this.board.length;
cols = this.board[0].length; //获取行和列的数目 for(int i = 0; i < rows; i++){
traver(i, 0); //第一列
traver(i, cols - 1); //最后一列
}
for(int i = 0; i < cols; i++){
traver(0, i); //第一行
traver(rows - 1, i); //最后一行
}
//遍历整个数组
for(int i = 0; i < rows;i++){
for(int j = 0; j < cols; j++){
board[i][j] = this.board[i][j] == 'Z' ? 'O' : 'X';
}
}
} /**
* 对x,y所指的单元进行BFS
* @param x
* @param y
*/
public void traver(int x, int y){
add(x, y);
while(!this.queue.isEmpty()){
int head = queue.poll(); //出队列
int temp_x = head / cols;
int temp_y = head % cols;
add(temp_x - 1, temp_y);
add(temp_x + 1, temp_y);
add(temp_x, temp_y - 1);
add(temp_x, temp_y + 1); //flood fill算法的体现
}
} /**
* x,y所指的单元如果是'o'放到队列中,x * cols + y
* @param x
* @param y
*/
public void add(int x, int y){
if(x >= 0 && x < rows && y >= 0 && y < cols && this.board[x][y] == 'O')
{
this.queue.add(x * cols + y);
this.board[x][y] = 'Z';
}
} }
BFS, FLOOD FILL...待续
参考：http://blog.csdn.net/pickless/article/details/12074363