[一道中等难度题] 被围绕的区域

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

点此在线做题

样例 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;
    }
}

更多题解参见