leetcode 130. Surrounded Regions | 130. 被围绕的区域(DFS递归“感染“思路)

x33g5p2x  于2021-11-12 转载在 其他  
字(1.1k)|赞(0)|评价(0)|浏览(145)

题目

https://leetcode.com/problems/surrounded-regions/

题解

Related Topics 说是并查集问题,然而我并没有用到。
带有 visited 数组的 DFS 时间复杂度应该是 O(M*N),因为每个坐标只被 visit 过 2 遍。

有点像围棋,只要我是活的,那么我能伸展到的位置就都是活的。
最初始的时候,有哪些是活的呢?那就是所有边沿上的 O。让它们去 DFS 做伸展,所以这是一个感染的过程。

或者可以这样想,只有能和上下左右边缘 接壤 的 ‘O’ 能够存活,所以不用去管中间的 O,只要让活着的 O,去感染相邻上下左右的 O,被感染的 O 就能存活,最后没有被感染的 O 就会挂掉,变成 X。

class Solution {
    int M, N;

    public void solve(char[][] board) {
        M = board.length;
        N = board[0].length;
        
        // 从4个边缘向内部"感染"
        boolean[][] visited = new boolean[M][N];
        boolean[][] alive = new boolean[M][N];
        for (int i = 0; i < M; i++) {
            dfs(board, i, 0, alive, visited);
            dfs(board, i, N - 1, alive, visited);
        }
        for (int j = 0; j < N; j++) {
            dfs(board, 0, j, alive, visited);
            dfs(board, M - 1, j, alive, visited);
        }
        
        // build return matrix
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!alive[i][j]) board[i][j] = 'X';
            }
        }
    }

    public void dfs(char[][] board, int i, int j, boolean[][] alive, boolean[][] visited) {
        if (i < 0 || i == M || j < 0 || j == N || visited[i][j]) return;
        visited[i][j] = true;
        if (board[i][j] == 'O') {
            alive[i][j] = true;
            dfs(board, i - 1, j, alive, visited);
            dfs(board, i + 1, j, alive, visited);
            dfs(board, i, j - 1, alive, visited);
            dfs(board, i, j + 1, alive, visited);
        }
    }
}

相关文章

微信公众号

最新文章

更多