Leetcode--Java--130. 被围绕的区域

题目描述

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

样例描述

思路

Flood Fill算法 + 逆向思维 核心：从内部开始dfs不好搜索，从边界开始dfs搜索，搜查区域的范围更方便

1. 从边界开始搜索，将边界的O都进行标记成#。
2. 再次遍历，遇到O就标记成X。
3. 转化为判断边界问题。(注意是每次都要判断元素是否在边界，所以isEdge不能放在最外面)
4. 注意不在边界，但是与边界相连接也不算被围绕！这就是为什么要dfs去探索。

代码

class Solution {
          
   
    public void solve(char[][] board) {
          
   
        if (board == null || board[0].length == 0) return;
       int m = board.length, n = board[0].length;
     
       //搜索边界的O进行标记
       for (int i = 0; i < m; i ++ ) {
          
   
           for (int j = 0; j < n; j ++ ) {
          
   
                 boolean isEdge = false;
               //判断是边界
               if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
          
   
                   isEdge = true;
               }
               //如果是边界，并且是O就进行标记成#
               if (isEdge && board[i][j] == O) {
          
   
                   //从边界开始探索没被围绕的区域
                   dfs(board, i, j);
               }
           }
       }
       //随后碰到O就标记为X，遇到#就标记回O
       for (int i = 0; i < m; i ++ ) {
          
   
            for (int j = 0; j < n; j ++ ) {
          
   
                if (board[i][j] == O) {
          
   
                    board[i][j] = X;
                }
                if (board[i][j] == #) {
          
   
                    board[i][j] = O;
                }
            }
       }
    }
 
    public void dfs(char[][] board, int i, int j) {
          
   
        //越界，为X，或者已经标记成#就直接返回
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == # || board[i][j] == X) return;

        //标记成#
        board[i][j] = #;
        //四个方向遍历,上右下左
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j + 1);
        dfs(board, i, j - 1);
    }
}