type
status
date
slug
summary
tags
category
icon
password
创建时间
Nov 14, 2024 03:08 AM
阿里 - 2024/11/12
岛屿问题，被 X 包住的 O 全部改成 X
示例 1:
输入：
board = new char[][]{
{'X', 'X', 'X', 'X'},
{'X', 'O', 'O', 'X'},
{'X', 'X', 'O', 'X'},
{'X', 'O', 'X', 'X'}
};
输出：
board = new char[][]{
{'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X'}
};
200. 岛屿数量
给你一个由
'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
在每个点尝试使用 DFS 算法，利用 DFS 算法得到连通的岛屿，并在岛屿上做标记。当岛屿不连通时，我们需要再次使用 DFS。最后使用 DFS 的次数就是岛屿的数量。
130. 被围绕的区域
给你一个
m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：- 连接：一个单元格与水平或垂直方向上相邻的单元格连接。
- 区域：连接所有
'O'的单元格来形成一个区域。
- 围绕：如果您可以用
'X'单元格 连接这个区域，并且区域中没有任何单元格位于board边缘，则该区域被'X'单元格围绕。
通过将输入矩阵
board 中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。这道题与“岛屿数量”是十分相似的。不过在处理上会有细微的小差别。我们在“岛屿数量”中是将每个点都遍历了，而在这道题我们是只从边缘位置出发进行 DFS。从边缘遍历标记的区域，是没有办法被包围的。这样我们就区分了三个区域。
最后，遍历整个网格，做点小处理即可。
695. 岛屿的最大面积
给你一个大小为
m x n 的二进制矩阵 grid 。岛屿 是由一些相邻的
1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。岛屿的面积是岛上值为
1 的单元格的数目。计算并返回
grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。有返回值的 dfs，加上值就行了。和前面的题是相同的逻辑。
463. 岛屿的周长
给定一个
row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
这题就比较简单了，题中已经说明了恰好有一个岛屿。我们就不需要去 dfs 判断岛屿数量什么的。直接开始遍历，然后判断当前岛屿周围有没有其他的岛屿相邻，如果有就要减去对应的边。最后求和就能得到答案。
1254. 统计封闭岛屿的数目
二维矩阵
grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。请返回 封闭岛屿 的数目。
本题相当于 “被围绕的区域” + “岛屿数量” 的结合题
1905. 统计子岛屿
给你两个
m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。如果
grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。请你返回
grid2 中 子岛屿 的 数目 。我的思路是先将相交部分的 grid2 改变标志，然后对改变标记的 grid2 做 DFS，判断周围是否与 1 相邻，如果有相邻说明不是包含关系。
📎 参考
- 无