跳至主要內容

130. 被围绕的区域


130. 被围绕的区域open in new window

🟠   🔖  深度优先搜索 广度优先搜索 并查集 数组 矩阵  🔗 力扣open in new window LeetCodeopen in new window

题目

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岛屿数量open in new window[✓]深度优先搜索 广度优先搜索 并查集 2+
286墙与门 🔒open in new window广度优先搜索 数组 矩阵