1、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以及与边界O相连的O都标记为*，然后将其他的O都变为X，最后将N重新变为O即可
深度优先搜索DFS：
public class solution { public void solve(char[][] board) { if(board.length <= 2 || board[0].length<=2) return; int row=board.length; int col=board[0].length; for(int i=0;i<row;i++) { DFS(board,i,0); DFS(board,i,col-1); } for(int i=0;i<col;i++) { DFS(board,0,i); DFS(board,row-1,i); } for(int i =0;i<row;i++) { for(int j=0;j<col;j++) { if(board[i][j] == 'O') board[i][j] ='X'; if(board[i][j] == '*') board[i][j] ='O'; } } } void DFS(char[][] board,int i,int j) { if(i<0 || i>=board.length || j<0 || j>=board[0].length) return; if(board[i][j] == 'X') return; if(board[i][j] == 'O') { board[i][j] == '*'; DFS(board,i-1,j); DFS(board,i+1,j); DFS(board,i,j-1); DFS(board,i,j+1); } } }