Kimi LeetCode 130. 被围绕的区域 Java实现

130. 被围绕的区域

思路：直接从边界内侧做DFS会陷入"如何知道是否被包围"的困境。换个角度——所有与边界相连的 ‘O’ 都不可能被包围。所以：

DFS 实现

class Solution {
private int m, n;

public void solve(char[][] board) {
if (board == null || board.length == 0) return;
m = board.length;
n = board[0].length;

// 从上下两条边界的 'O' 出发
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O') dfs(board, 0, j);
if (board[m – 1][j] == 'O') dfs(board, m – 1, j);
}
// 从左右两条边界的 'O' 出发
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') dfs(board, i, 0);
if (board[i][n – 1] == 'O') dfs(board, i, n – 1);
}

// 还原 + 填充
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') board[i][j] = 'X'; // 被围绕
else if (board[i][j] == '#') board[i][j] = 'O'; // 边界连通，保留
}
}
}

private void dfs(char[][] board, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return;
board[i][j] = '#';
dfs(board, i + 1, j);
dfs(board, i – 1, j);
dfs(board, i, j + 1);
dfs(board, i, j – 1);
}
}

复杂度：时间 O(m \\times n)，每个格子最多访问一次；空间 O(m \\times n)，递归栈最坏情况。

BFS 实现（避免递归栈溢出，适合超大矩阵）

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
int m = board.length, n = board[0].length;
Deque<int[]> queue = new ArrayDeque<>();
int[][] dirs = {{1,0},{–1,0},{0,1},{0,–1}};

// 把所有边界上的 'O' 入队
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') { board[i][0] = '#'; queue.offer(new int[]{i, 0}); }
if (board[i][n–1] == 'O') { board[i][n–1] = '#'; queue.offer(new int[]{i, n–1}); }
}
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O') { board[0][j] = '#'; queue.offer(new int[]{0, j}); }
if (board[m–1][j] == 'O') { board[m–1][j] = '#'; queue.offer(new int[]{m–1, j}); }
}

// BFS 标记所有与边界连通的 'O'
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int[] d : dirs) {
int x = cur[0] + d[0], y = cur[1] + d[1];
if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
board[x][y] = '#';
queue.offer(new int[]{x, y});
}
}
}

// 还原 + 填充
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
else if (board[i][j] == '#') board[i][j] = 'O';
}
}
}
}

关键点

• 核心转化：不判断"哪些 O 被包围"，而是反过来标记"哪些 O 一定不被包围"（与边界连通），剩下的就是要填充的。
• DFS 写法简洁但最坏情况（全是 ‘O’）递归深度可达 m \\times n，可能栈溢出，面试时可主动提出 BFS 替代。
• 进阶方案：并查集，把所有边界 ‘O’ 和一个虚拟的"边界哨兵"节点 union，最后检查每个格子是否与哨兵连通。时间复杂度同样 O(mn)，面试中作为扩展思路提及即可。
•