被围绕的区域

发表于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

LeetCode每日一题，130. Surrounded Regions

先看题目描述

大意就是将被 X 围起来的 O 改为 X，而与边界连接的 O 不变

算法和思路

这题一开始不会，看了题解才懂

题目解释中提到：任何边界上的 O 都不会被填充为 X，我们可以想到，所有不被包围的 O 都直接或间接与边界上的 O 相连，我们可以利用这个性质判断 O 是否在边界上

  • 对于每一个边界上的 O，我们以它为起点，标记所有与它直接或间接相连的字母 O 为 #；
  • 最后我们遍历这个矩阵，对于每一个字母：
    • 如果该字母被标记过，即被标记为 #，则该字母为没有被字母 X 包围的字母 O，我们将其还原为字母 O；
    • 如果该字母没有被标记过，则该字母为被字母 X 包围的字母 O，我们将其修改为字母 X

算法源码

下面是根据题解的 dfs递归法 实现的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public void solve(char[][] board) {
        if (board.length == 0) return;
        if (board[0].length == 0) return;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean isEdge = i == 0 || i == m - 1 || j == 0 || j == n - 1;
                if (isEdge && board[i][j] == 'O') {
                    dfs(board, i, j);
                }
            }
        }
        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) {
        int m = board.length;
        int n = board[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] == 'X' || board[i][j] == '#') return;
        board[i][j] = '#';
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    }
}