DEV Community
·
解决LeetCode的岛屿数量问题：深度优先搜索的深入探讨
💡
原文英文，约400词，阅读约需2分钟。
📝
内容提要
岛屿数量问题是深度优先搜索（DFS）在网格遍历中的经典应用。通过DFS，可以有效计算连接的“1”的组数，并直接修改输入网格以标记已访问的单元格。实现时，遍历网格，找到“1”时递增计数并进行DFS探索。时间复杂度为O(M×N)，空间复杂度为O(M×N)。
🎯
关键要点
- 岛屿数量问题是深度优先搜索（DFS）在网格遍历中的经典应用。
- 通过DFS，可以有效计算连接的'1'的组数，并直接修改输入网格以标记已访问的单元格。
- 问题理解：需要计算不同岛屿的数量，岛屿定义为连接的'1'的组。
- 实现策略：使用DFS探索连接组件，修改输入网格以跟踪已访问的单元格。
- 主要功能：遍历网格中的每个单元格，找到'1'时递增计数并开始DFS探索。
- DFS辅助函数：检查边界条件，验证当前单元格是否为岛屿的一部分，标记已访问的单元格，四个方向探索。
- 边缘情况：空网格、单行/单列网格、没有岛屿的网格、全是岛屿的网格。
- 复杂度分析：时间复杂度为O(M × N)，空间复杂度为O(M × N)。
- 优化：直接修改输入网格以标记已访问的单元格，节省空间，简化逻辑，保持连接组件属性。
➡️
