给一个二维的矩阵，包含 'X' 和 'O', 找到所有被 'X' 围绕的区域，并用 'X' 替换其中所有的 'O'。

在线评测地址：
https://www.lintcode.com/problem/surrounded-regions/?utm_source=sc-tianchi-sz0819

样例 1:

输入:
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
样例 2:

输入:
X X X X
X O O X
X O O X
X O X X
输出:
X X X X
X O O X
X O O X
X O X X
【题解】

算法：DFS

思路：先从外围开始，只有身处外围的 O 是无法被包围的，同理，与一个无法被包围的 O 相连的 O 也是无法被包围的。

从外围开始，若遇到边界的 O，则将其标记为 *，意味无法被包围的 O
依次对外圈的“O”的四个方向做DFS，将其可以到达O临时设置为*
最后，遍历数组，
将无法被包围的O，也就是此时被标记为 * 改为 O；
X 不变；
将可以被包围的区域，即没被标记过的O 变为X
复杂度分析

时间复杂度O(n*m)
搜索一次图即可
空间复杂度O(n*m)
图的大小
public class Solution {

/**
 * @param board a 2D board containing 'X' and 'O'
 * @return void
 */
public void surroundedRegions(char[][] board) {
    if (board == null || board.length == 0 || board[0].length == 0) {
        return ;
    }
    int n = board.length,m = board[0].length;
    //四周向中间搜
    for (int i = 0; i < n;i++) {
        for (int j = 0;j < m;j++) {
            if (!is_border(i,j,n,m)) {
                continue;
            }
            if (board[i][j] == 'O') {
                dfs(board , i , j);
            }
        }
    }
    
    //遍历图，更新结果
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            if (board[i][j] == 'O') {
                board[i][j] = 'X';
            }
            else if (board[i][j] == '*') {
                board[i][j] = 'O'; 
            }
        }
    }
}

public void dfs(char[][] board , int x , int y){
    //保证当前点在图中
    if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) {
        return ;
    }
    if (board[x][y] != 'O') {
        return ;
    }
    board[x][y] = '*';
    dfs(board , x + 1, y);
    dfs(board , x - 1, y);
    dfs(board , x , y + 1);
    dfs(board , x , y - 1);
}
public boolean is_border(int x,int y,int n,int m) {//判断是否边界
    if (x == 0 || y == 0 || x == n - 1||y == m - 1) {
        return true;
    }
    return false;
}

}
更多题解参见九章算法官网：
https://www.jiuzhang.com/solution/surrounded-regions/?utm_source=sc-tianchi-sz0819