ImCaO's Blog
·
岛屿类问题的通用解法、DFS 遍历框架
💡
原文中文，约7000字，阅读约需17分钟。
📝
内容提要
岛屿问题是网格结构中的典型深度优先搜索（DFS）问题，主要涉及岛屿数量、面积和周长等变种。通过标记已遍历的格子，可以有效避免重复访问，从而解决问题。本文介绍了岛屿问题的DFS遍历框架及具体解法，强调理解网格结构和DFS的重要性。
🎯
关键要点
- 岛屿问题是网格结构中的典型深度优先搜索（DFS）问题，主要涉及岛屿数量、面积和周长等变种。
- 网格结构由 m × n 个小方格组成，每个格子与其上下左右四个方格相邻，数字为 0 的格子代表海洋，数字为 1 的格子代表陆地。
- DFS 的基本结构包括访问相邻结点和判断 base case，网格结构的相邻结点为上下左右四个。
- 为了避免重复遍历，需标记已遍历的格子，将格子的值改为 2，以区分海洋格子和已遍历的陆地格子。
- 岛屿问题的解法包括对每个岛屿进行 DFS 遍历以求出面积，填海造陆问题需要两遍 DFS 来计算最大岛屿面积。
- 岛屿的周长可以通过 DFS 遍历计算，返回时根据坐标超出网格范围或当前格子是海洋格子来增加周长。
❓
延伸问答
岛屿问题的基本定义是什么？
岛屿问题是网格结构中的典型深度优先搜索（DFS）问题，主要涉及岛屿的数量、面积和周长等变种。
如何在网格中实现深度优先搜索（DFS）？
在网格中实现DFS需要访问相邻的四个格子，并判断是否超出网格范围，通常通过递归实现。
如何避免在DFS遍历中重复访问格子？
通过标记已遍历的格子，将其值改为2，以区分海洋格子和已遍历的陆地格子，从而避免重复访问。
岛屿的面积如何计算？
岛屿的面积通过对每个岛屿进行DFS遍历，遍历到一个格子时面积加一，最终得到岛屿的总面积。
填海造陆问题的基本思路是什么？
填海造陆问题的思路是计算所有岛屿的面积，并标记岛屿的索引，寻找哪个海洋格子可以连接最大面积的岛屿。
如何计算岛屿的周长？
岛屿的周长通过DFS遍历计算，返回时根据坐标超出网格范围或当前格子是海洋格子来增加周长。
➡️
