## 题目地址

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

## 题目描述

Given a 2D board containing `'X'` and `'O'`(the letter O), capture all regions surrounded by `'X'`.

A region is captured by flipping all `'O'`s into `'X'`s in that surrounded region.

Example:

``````X X X X
X O O X
X X O X
X O X X
``````

After running your function, the board should be:

``````X X X X
X X X X
X X X X
X O X X
``````

Explanation:

Surrounded regions shouldn’t be on the border, which means that any `'O'` on the border of the board are not flipped to `'X'`. Any `'O'` that is not on the border and it is not connected to an `'O'` on the border will be flipped to `'X'`. Two cells are connected if they are adjacent cells connected horizontally or vertically.

## 思路

``````class Solution {
public:
void solve(vector<vector<char> >& board) {
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[i].size(); ++j) {
if ((i == 0 || i == board.size() - 1 || j == 0 || j == board[i].size() - 1) && board[i][j] == 'O')
solveDFS(board, i, j);
}
}
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[i].size(); ++j) {
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == '\$') board[i][j] = 'O';
}
}
}
void solveDFS(vector<vector<char> > &board, int i, int j) {
if (board[i][j] == 'O') {
board[i][j] = '\$';
if (i > 0 && board[i - 1][j] == 'O')
solveDFS(board, i - 1, j);
if (j < board[i].size() - 1 && board[i][j + 1] == 'O')
solveDFS(board, i, j + 1);
if (i < board.size() - 1 && board[i + 1][j] == 'O')
solveDFS(board, i + 1, j);
if (j > 0 && board[i][j - 1] == 'O')
solveDFS(board, i, j - 1);
}
}
};
``````

``````class Solution {
public:
void solve(vector<vector<char>>& board) {
if (board.empty() || board[0].empty()) return;
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
if (board[i][j] == 'O') dfs(board, i , j);
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == '\$') board[i][j] = 'O';
}
}
}
void dfs(vector<vector<char>> &board, int x, int y) {
int m = board.size(), n = board[0].size();
vector<vector<int>> dir{{0,-1},{-1,0},{0,1},{1,0}};
board[x][y] = '\$';
for (int i = 0; i < dir.size(); ++i) {
int dx = x + dir[i][0], dy = y + dir[i][1];
if (dx >= 0 && dx < m && dy > 0 && dy < n && board[dx][dy] == 'O') {
dfs(board, dx, dy);
}
}
}
};
``````

``````class Solution {
public:
void solve(vector<vector<char>>& board) {
if (board.empty() || board[0].empty()) return;
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i != 0 && i != m - 1 && j != 0 && j != n - 1) continue;
if (board[i][j] != 'O') continue;
board[i][j] = '\$';
queue<int> q{{i * n + j}};
while (!q.empty()) {
int t = q.front(), x = t / n, y = t % n; q.pop();
if (x >= 1 && board[x - 1][y] == 'O') {board[x - 1][y] = '\$'; q.push(t - n);}
if (x < m - 1 && board[x + 1][y] == 'O') {board[x + 1][y] = '\$'; q.push(t + n);}
if (y >= 1 && board[x][y - 1] == 'O') {board[x][y - 1] = '\$'; q.push(t - 1);}
if (y < n - 1 && board[x][y + 1] == 'O') {board[x][y + 1] = '\$'; q.push(t + 1);}
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == '\$') board[i][j] = 'O';
}
}
}
};
``````

## 关键点解析

• 二维数组DFS解题模板
• 转化问题为`连通区域问题`
• 直接mutate原数组，节省空间

## 代码

• 语言支持：JS，Python3
``````

/*
* @lc app=leetcode id=130 lang=javascript
*
* [130] Surrounded Regions
*/
// 将O以及周边的O转化为A
function mark(board, i, j, rows, cols) {
if (i < 0 || i > rows - 1 || j < 0 || j > cols - 1 || board[i][j] !== "O")
return;

board[i][j] = "A";
mark(board, i + 1, j, rows, cols);
mark(board, i - 1, j, rows, cols);
mark(board, i, j + 1, rows, cols);
mark(board, i, j - 1, rows, cols);
}
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function(board) {
const rows = board.length;
if (rows === 0) return [];
const cols = board[0].length;

for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (i === 0 || i == rows - 1 || j === 0 || j === cols - 1) {
mark(board, i, j, rows, cols);
}
}
}

for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (board[i][j] === "O") {
board[i][j] = "X";
} else if (board[i][j] === "A") {
board[i][j] = "O";
}
}
}

return board;
};
``````

Python Code：

``````class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
# 如果数组长或宽小于等于2，则不需要替换
if len(board) <= 2 or len(board[0]) <= 2:
return

row, col = len(board), len(board[0])

def dfs(i, j):
"""
深度优先算法，如果符合条件，替换为A并进一步测试，否则停止
"""
if i < 0 or j < 0 or i >= row or j >= col or board[i][j] != 'O':
return
board[i][j] = 'A'

dfs(i - 1, j)
dfs(i + 1, j)
dfs(i, j - 1)
dfs(i, j + 1)

# 从外围开始
for i in range(row):
dfs(i, 0)
dfs(i, col-1)

for j in range(col):
dfs(0, j)
dfs(row-1, j)

# 最后完成替换
for i in range(row):
for j in range(col):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == 'A':
board[i][j] = 'O'
``````

### 思路3

#### 思路：

``````X X X X
X O O X
X X O X
X O O X
``````

• `bfs` 递归。可以想想二叉树中如何递归的进行层序遍历。
• `bfs` 非递归。一般用队列存储。
• `dfs` 递归。最常用，如二叉树的先序遍历。
• `dfs` 非递归。一般用 `stack`
那么基于上面这种想法，我们有四种方式实现。

#### dfs递归:

``````
class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 从边缘o开始搜索
boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
if (isEdge && board[i][j] == 'O') {
dfs(board, i, j);
}
}
}

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == '#') {
board[i][j] = 'O';
}
}
}
}

public void dfs(char[][] board, int i, int j) {
if (i < 0 || j < 0 || i >= board.length  || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') {
// board[i][j] == '#' 说明已经搜索过了.
return;
}
board[i][j] = '#';
dfs(board, i - 1, j); // 上
dfs(board, i + 1, j); // 下
dfs(board, i, j - 1); // 左
dfs(board, i, j + 1); // 右
}
}
``````

#### dsf 非递归:

``````
class Solution {
public class Pos{
int i;
int j;
Pos(int i, int j) {
this.i = i;
this.j = j;
}
}
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 从边缘第一个是o的开始搜索
boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
if (isEdge && board[i][j] == 'O') {
dfs(board, i, j);
}
}
}

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == '#') {
board[i][j] = 'O';
}
}
}
}

public void dfs(char[][] board, int i, int j) {
Stack<Pos> stack = new Stack<>();
stack.push(new Pos(i, j));
board[i][j] = '#';
while (!stack.isEmpty()) {
// 取出当前stack 顶, 不弹出.
Pos current = stack.peek();
// 上
if (current.i - 1 >= 0
&& board[current.i - 1][current.j] == 'O') {
stack.push(new Pos(current.i - 1, current.j));
board[current.i - 1][current.j] = '#';
continue;
}
// 下
if (current.i + 1 <= board.length - 1
&& board[current.i + 1][current.j] == 'O') {
stack.push(new Pos(current.i + 1, current.j));
board[current.i + 1][current.j] = '#';
continue;
}
// 左
if (current.j - 1 >= 0
&& board[current.i][current.j - 1] == 'O') {
stack.push(new Pos(current.i, current.j - 1));
board[current.i][current.j - 1] = '#';
continue;
}
// 右
if (current.j + 1 <= board[0].length - 1
&& board[current.i][current.j + 1] == 'O') {
stack.push(new Pos(current.i, current.j + 1));
board[current.i][current.j + 1] = '#';
continue;
}
// 如果上下左右都搜索不到,本次搜索结束，弹出stack
stack.pop();
}
}
}
``````

#### bfs 非递归:

`dfs` 非递归的时候我们用 `stack` 来记录状态，而 `bfs` 非递归，我们则用队列来记录状态。和 `dfs` 不同的是，dfs 中搜索上下左右，只要搜索到一个满足条件，我们就顺着该方向继续搜索，所以你可以看到 `dfs` 代码中，只要满足条件，就入 `Stack`，然后 `continue` 本次搜索，进行下一次搜索，直到搜索到没有满足条件的时候出 `stack`。而 `dfs` 中，我们要把上下左右满足条件的都入队，所以搜索的时候就不能 `continue`。大家可以对比下两者的代码，体会 `bfs``dfs` 的差异。

``````
class Solution {
public class Pos{
int i;
int j;
Pos(int i, int j) {
this.i = i;
this.j = j;
}
}
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 从边缘第一个是o的开始搜索
boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
if (isEdge && board[i][j] == 'O') {
bfs(board, i, j);
}
}
}

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == '#') {
board[i][j] = 'O';
}
}
}
}

public void bfs(char[][] board, int i, int j) {
board[i][j] = '#';
while (!queue.isEmpty()) {
Pos current = queue.poll();
// 上
if (current.i - 1 >= 0
&& board[current.i - 1][current.j] == 'O') {
board[current.i - 1][current.j] = '#';
// 没有continue.
}
// 下
if (current.i + 1 <= board.length - 1
&& board[current.i + 1][current.j] == 'O') {
board[current.i + 1][current.j] = '#';
}
// 左
if (current.j - 1 >= 0
&& board[current.i][current.j - 1] == 'O') {
board[current.i][current.j - 1] = '#';
}
// 右
if (current.j + 1 <= board[0].length - 1
&& board[current.i][current.j + 1] == 'O') {
board[current.i][current.j + 1] = '#';
}
}
}
}
``````

#### bfs 递归:

`bfs` 一般我们不会去涉及，而且比较绕，之前我们唯一 A 过的用 `bfs` 递归的方式是层序遍历二叉树的时候可以用递归的方式。

#### 并查集:

• `find(int m)`：这是并查集的基本操作，查找 `m` 的根节点。

• `isConnected(int m,int n)`：判断 `m``n` 两个点是否在一个连通区域。

• `union(int m,int n)`:合并 `m``n` 两个点所在的连通区域。

``````class UnionFind {
int[] parents;

public UnionFind(int totalNodes) {
parents = new int[totalNodes];
for (int i = 0; i < totalNodes; i++) {
parents[i] = i;
}
}
// 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
void union(int node1, int node2) {
int root1 = find(node1);
int root2 = find(node2);
if (root1 != root2) {
parents[root2] = root1;
}
}

int find(int node) {
while (parents[node] != node) {
// 当前节点的父节点 指向父节点的父节点.
// 保证一个连通区域最终的parents只有一个.
parents[node] = parents[parents[node]];
node = parents[node];
}

return node;
}

boolean isConnected(int node1, int node2) {
return find(node1) == find(node2);
}
}
``````

• 和边界上的 `O` 在一个连通区域内的。这些 `O` 我们保留。
• 不和边界上的 `O` 在一个连通区域内的。这些 `O` 就是被包围的，替换。

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

int rows = board.length;
int cols = board[0].length;

// 用一个虚拟节点, 边界上的O 的父节点都是这个虚拟节点
UnionFind uf = new UnionFind(rows * cols + 1);
int dummyNode = rows * cols;

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == 'O') {
// 遇到O进行并查集操作合并
if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
// 边界上的O,把它和dummyNode 合并成一个连通区域.
uf.union(node(i, j), dummyNode);
} else {
// 和上下左右合并成一个连通区域.
if (i > 0 && board[i - 1][j] == 'O')
uf.union(node(i, j), node(i - 1, j));
if (i < rows - 1 && board[i + 1][j] == 'O')
uf.union(node(i, j), node(i + 1, j));
if (j > 0 && board[i][j - 1] == 'O')
uf.union(node(i, j), node(i, j - 1));
if (j < cols - 1 && board[i][j + 1] == 'O')
uf.union(node(i, j), node(i, j + 1));
}
}
}
}
``````

评论
0 评论