題目

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

總結

以上是生活随笔為你收集整理的leetcode 130. Surrounded Regions | 130. 被围绕的区域（DFS递归“感染“思路）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。