[leetcode hot 150]第一百三十题，被围绕的区域

题目：

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：

• 连接：一个单元格与水平或垂直方向上相邻的单元格连接。
• 区域：连接所有 '0' 的单元格来形成一个区域。
• 围绕：如果您可以用 'X' 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕。

通过将输入矩阵 board 中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。

1. 初始化和边界检查：
   • 检查 board 是否为空或长度为零。
   • 获取矩阵的行数 m 和列数 n。
2. 标记边界上的 'O'：
   • 遍历矩阵的边界（第一行、最后一行、第一列、最后一列），对于每一个 'O'，使用 DFS 将其标记为 'B'。
3. DFS 方法：
   • 检查当前单元格是否在矩阵范围内，并且是否是 'O'。
   • 如果是 'O'，将其标记为 'B'。
   • 递归处理当前单元格的上下左右四个方向。
4. 替换和还原：
   • 遍历整个矩阵，将所有的 'O' 替换为 'X'（这些是被围绕的区域）。
   • 将所有的 'B' 还原为 'O'（这些是边界上的或连接到边界的 'O'）。

import java.util.Arrays;

public class no_130 {
    public static void main(String[] args) {
        char[][] board = {
                {'X', 'X', 'X', 'X'},
                {'X', 'O', 'O', 'X'},
                {'X', 'X', 'O', 'X'},
                {'X', 'O', 'X', 'X'}
        };
        solve(board);
        for (char[] chars : board) {
            System.out.println(Arrays.toString(chars));
        }


    }

    public static void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }

        int m = board.length;
        int n = board[0].length;

        for (int i = 0; i < m; i++) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            dfs(board, 0, j);
            dfs(board, m - 1, j);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == 'B') {
                    board[i][j] = 'O';
                }

            }
        }
    }

    private static void dfs(char[][] board, int i, int j) {
        int m = board.length;
        int n = board[0].length;

        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
            return;
        }

        board[i][j] = 'B';

        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    }
}

本题关键：只要这个区域有一个点在边界上，那么这个区域肯定不能被围绕，除了边界的区域其他所有区域都是被围绕的，改为X。

原文地址：https://blog.csdn.net/weixin_45201305/article/details/140234462

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！