ImCaO's Blog
·
岛屿类问题的通用解法、DFS 遍历框架
内容提要
岛屿问题是网格结构中的典型深度优先搜索（DFS）问题，主要涉及岛屿数量、面积和周长等变种。通过标记已遍历的格子，可以有效避免重复访问，从而解决问题。本文介绍了岛屿问题的DFS遍历框架及具体解法，强调理解网格结构和DFS的重要性。
关键要点
-
岛屿问题是网格结构中的典型深度优先搜索（DFS）问题，主要涉及岛屿数量、面积和周长等变种。
-
网格结构由 m × n 个小方格组成，每个格子与其上下左右四个方格相邻，数字为 0 的格子代表海洋，数字为 1 的格子代表陆地。
-
DFS 的基本结构包括访问相邻结点和判断 base case，网格结构的相邻结点为上下左右四个。
-
为了避免重复遍历，需标记已遍历的格子，将格子的值改为 2，以区分海洋格子和已遍历的陆地格子。
-
岛屿问题的解法包括对每个岛屿进行 DFS 遍历以求出面积，填海造陆问题需要两遍 DFS 来计算最大岛屿面积。
-
岛屿的周长可以通过 DFS 遍历计算，返回时根据坐标超出网格范围或当前格子是海洋格子来增加周长。
延伸解读
DFS遍历的基本结构
在网格结构中，DFS遍历的基本结构与二叉树相似，但需要注意相邻节点的定义。网格中的每个格子有四个相邻格子（上下左右），而不是二叉树的两个子节点。这种结构的复杂性要求开发者在实现时更加小心，确保不会出现越界或重复遍历的情况。
避免重复遍历的策略
在解决岛屿问题时，避免重复遍历是关键。通过将已遍历的陆地格子标记为不同的值（如2），可以有效防止DFS陷入无限循环。这种标记方法不仅提高了算法效率，也减少了潜在的错误，确保每个格子只被访问一次。
填海造陆问题的复杂性
填海造陆问题相比于基本的岛屿面积计算更为复杂，因为它涉及到对多个岛屿的合并。需要在DFS遍历中记录每个岛屿的面积，并在计算时避免重复计入同一岛屿的面积。这种额外的复杂性要求开发者在实现时更加细致，确保算法的正确性。
延伸问答
岛屿问题的基本定义是什么？
岛屿问题是网格结构中的典型深度优先搜索（DFS）问题，主要涉及岛屿的数量、面积和周长等变种。
如何在网格中实现深度优先搜索（DFS）？
在网格中实现DFS需要访问相邻的四个格子，并判断是否超出网格范围，通常通过递归实现。
如何避免在DFS遍历中重复访问格子？
通过标记已遍历的格子，将其值改为2，以区分海洋格子和已遍历的陆地格子，从而避免重复访问。
岛屿的面积如何计算？
岛屿的面积通过对每个岛屿进行DFS遍历，遍历到一个格子时面积加一，最终得到岛屿的总面积。
填海造陆问题的基本思路是什么？
填海造陆问题的思路是计算所有岛屿的面积，并标记岛屿的索引，寻找哪个海洋格子可以连接最大面积的岛屿。
如何计算岛屿的周长？
岛屿的周长通过DFS遍历计算，返回时根据坐标超出网格范围或当前格子是海洋格子来增加周长。
