AlgoViz Lab交互式算法学习Algorithms first
被围绕的区域 · 交互式算法学习
把不与边界相连的 O 区域填成 X。
#130 · 图
被围绕的区域
Surrounded Regions
board = [[X,X,X,X],[X,O,O,X],[X,X,O,X],[X,O,X,X]]矩阵3 个关键状态
步骤 1边界 O 标记为安全 S。
S at (3,1)X0,0
X0,1
X0,2
X0,3
X1,0
O1,1
O1,2
X1,3
X2,0
X2,1
O2,2
X2,3
X3,0
O3,1
X3,2
X3,3
推荐
从边界反向标记
时间
O(mn)空间 O(mn)先从边界 O 标记所有安全区域，剩余 O 才翻转。
1function solve(b) {2 const m = b.length,3 n = b[0].length;4 5 function dfs(r, c) {6 if (b[r]?.[c] !== 'O') return;7 b[r][c] = 'S';8 dfs(r + 1, c);9 dfs(r - 1, c);10 dfs(r, c + 1);11 dfs(r, c - 1)12 }13 for (let r = 0; r < m; r++) {14 dfs(r, 0);15 dfs(r, n - 1)16 }17 for (let c = 0; c < n; c++) {18 dfs(0, c);19 dfs(m - 1, c)20 }21 for (let r = 0; r < m; r++)22 for (let c = 0; c < n; c++) b[r][c] = b[r][c] === 'S' ? 'O' : b[r][c] === 'O' ? 'X' : b[r][c];23}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 private final int[] dirs = {-1, 0, 1, 0, -1};3 private char[][] board;4 private int m;5 private int n;6 7 public void solve(char[][] board) {8 m = board.length;9 n = board[0].length;10 this.board = board;11 for (int i = 0; i < m; ++i) {12 dfs(i, 0);13 dfs(i, n - 1);14 }15 for (int j = 0; j < n; ++j) {16 dfs(0, j);17 dfs(m - 1, j);18 }19 for (int i = 0; i < m; ++i) {20 for (int j = 0; j < n; ++j) {21 if (board[i][j] == '.') {22 board[i][j] = 'O';23 } else if (board[i][j] == 'O') {24 board[i][j] = 'X';25 }26 }27 }28 }29 30 private void dfs(int i, int j) {31 if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {32 return;33 }34 board[i][j] = '.';35 for (int k = 0; k < 4; ++k) {36 dfs(i + dirs[k], j + dirs[k + 1]);37 }38 }39}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
被围绕的区域 · 解法对比
把不与边界相连的 O 区域填成 X。
- 测试用例
board = [[X,X,X,X],[X,O,O,X],[X,X,O,X],[X,O,X,X]]- 题目分类
- 图
- 解法对比
- 2
每个 O 搜索能否到边界
对每个 O 单独 DFS，若整块不触边则翻转。
- 时间
O((mn)²)- 空间
O(mn)
从边界反向标记
先从边界 O 标记所有安全区域，剩余 O 才翻转。
- 时间
O(mn)- 空间
O(mn)