题目

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);
        }
    }
}