给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X
解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终
都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

 

思路：

对边界进行dfs  将边界上的‘O’以及和‘O’相连的’O‘变为S   至此  剩下的所有O都是被包围的O  可以改写成‘S’

详细解释看代码注释

public void solve(char[][] board) {
	        // 把边界上 的 'O' 变为 'S'
	        // 遍历整个数组  把 'O' 变为 'X'
	        // 遍历整个数组 再把 'S' 变为 'O'
	        
	        if(board.length == 0 || board[0].length == 0)
	            return;
	        int h = board.length;
	        int w = board[0].length;
	        // 对边界上 的 'O'以及和'O'相连的'O'进行dfs     变为 'S' 
	        for(int i = 0; i < h; i++){
	            dfs(board, i, 0);    //第一列
	            dfs(board, i, w-1);  //最后一列
	        }
	        for(int j = 0; j < w; j++){
	            dfs(board, 0, j);   //第一行
	            dfs(board, h-1, j); //最后一列
	        }
	        
	        //遍历所有的位置   将S还元原   
	        for(int i = 0; i < h; i++){
	            for(int j = 0; j < w; j++){
	            	//现在找到的O 不可能和边界相连  因为相连的已经变为S了
	                if(board[i][j] == 'O') 
	                	board[i][j] = 'X';           //此时找到的'O'都是被包围的'O'
	                else if(board[i][j] == 'S') 
	                	board[i][j] = 'O';           //找到的S  还原成O
	            }
	        }
	    }
	    
	    private void dfs(char[][] board, int i, int j){
	        int h = board.length;
	        int w = board[0].length;
	        if(i >= 0 && i < h && j >=0 && j < w && board[i][j] == 'O'){
	        	//将'O'变为'S'
	            board[i][j] = 'S';
	            dfs(board, i-1, j);
	            dfs(board, i+1, j);
	            dfs(board, i, j-1);
	            dfs(board, i, j+1);
	        }
	    }