130. 被围绕的区域
130. 被围绕的区域
🟠 🔖 深度优先搜索
广度优先搜索
并查集
数组
矩阵
🔗 力扣
LeetCode
题目
Given an m x n
matrix board
containing 'X'
and 'O'
, capture all regions that are 4-directionally surrounded by 'X'
.
A region is captured by flipping all 'O'
s into 'X'
s in that surrounded region.
Example 1:
Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.
Example 2:
Input: board = [["X"]]
Output: [["X"]]
Constraints:
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j]
is'X'
or'O'
.
题目大意
给你一个 m x n
的矩阵 board
,由若干字符 'X'
和 'O'
组成,捕获 所有 被围绕的区域:
- 连接: 一个单元格与水平或垂直方向上相邻的单元格连接。
- 区域:连接所有
'O'
的单元格来形成一个区域。 - 围绕: 如果您可以用
'X'
单元格 连接这个区域,并且区域中没有任何单元格位于board
边缘,则该区域被'X'
单元格围绕。
通过将输入矩阵 board
中的所有 'O'
替换为 'X'
来 捕获被围绕的区域。
解题思路
首选选择出与岸边相连的岛屿并标记为 F
,然后把内部封闭的岛屿全部置为 X,最后把 F
置为 O
。
代码
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function (board) {
const dfs = (board, i, j) => {
const m = board.length,
n = board[0].length;
if (i < 0 || i >= m || j < 0 || j >= n) {
return;
}
if (board[i][j] !== 'O') {
return;
}
board[i][j] = 'F';
dfs(board, i - 1, j);
dfs(board, i + 1, j);
dfs(board, i, j - 1);
dfs(board, i, j + 1);
};
const m = board.length,
n = board[0].length;
// 选择出与岸边相连的岛屿并标记为 F
for (let 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 (let 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);
}
// 把内部封闭的岛屿全部置为 X,把 F 置为 O
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (board[i][j] == 'F') {
board[i][j] = 'O';
} else {
board[i][j] = 'X';
}
}
}
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
200 | 岛屿数量 | [✓] | 深度优先搜索 广度优先搜索 并查集 2+ | |
286 | 墙与门 🔒 | 广度优先搜索 数组 矩阵 |