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.
X X X X
X O O X
X X O X
X O X X
After capture all regions surrounded by ‘X‘, the board should be:
X X X X
X X X X
X X X X
X O X X
代码如下，这次用的java因为c++其实并没有看过多少，只了解一点C的。
思路就是从边界的‘O’开始搜索与其相连的‘O’，并标记， 直到所有边界上的‘O’都被搜索过，没有被标记的就是被包围的。
本来想用BFS的，但是刚写到方法名想到其实不用bfs就能搞定，递归的出口也很明显，于是。。 
1 public class Solution { 2 /** 3 * @param board a 2D board containing ‘X‘ and ‘O‘ 4 * @return void 5 */ 6 int flag[][]= new int[1000][1000]; 7 int x = 0; 8 int y = 0; 9 public void surroundedRegions(char[][] board) { 10 // Write your code here 11 this.x = board.length; 12 if(board.length == 0) return ; 13 this.y = board[0].length; 14 for(int i = 0; i<x; i++) { 15 if(board[i][0] == ‘O‘) bfs(board,i,0); 16 if(board[i][this.y-1] == ‘O‘) bfs(board,i,this.y-1); 17 } 18 for(int i = 0; i<y ;i++) { 19 if(board[0][i] == ‘O‘) bfs(board,0,i); 20 if(board[this.x-1][i] == ‘O‘) bfs(board,this.x-1,i); 21 } 22 23 for(int i = 0; i < x; i++) { 24 for(int j = 0; j < y; j++) { 25 if(flag[i][j] == 0 && board[i][j] == ‘O‘) { 26 board[i][j] = ‘X‘; 27 } 28 } 29 } 30 } 31 32 public void bfs(char[][] board, int i, int j) { 33 if(i<x && i>=0 && j<y && j>=0 && flag[i][j] == 0 && board[i][j] == ‘O‘ ) { 34 this.flag[i][j] = 1; 35 bfs(board,i+1,j); 36 bfs(board,i,j+1); 37 bfs(board,i-1,j); 38 bfs(board,i,j-1); 39 } 40 } 41 }
原文：http://www.cnblogs.com/FJH1994/p/4999357.html
