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	墙与门		广度优先搜索 数组 矩阵