C++面试宝典第20题：计算岛屿数量-Toy模板网

这篇具有很好参考价值的文章主要介绍了C++面试宝典第20题：计算岛屿数量。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

在二维网格地图上，'1' 表示陆地，'0' 表示水域。如果相邻的陆地可以水平或垂直连接，则它们属于同一块岛屿。请进行编码，统计地图上的岛屿数量。比如：下面的二维网格地图，其岛屿数量为3。

C++面试宝典第20题：计算岛屿数量,C++面试宝典100题,c++,面试,深度优先,广度优先,岛屿数量

解析

这道题主要考察应聘者对深度优先搜索、广度优先搜索、二维数组和矩阵操作、边界条件判断、递归等知识点的理解和掌握。

深度优先搜索：也就是Deep First Search，简称为DFS，这是一种用于遍历或搜索树或图的算法。对于每个节点，算法会尽可能深地搜索树的分支。当节点V的所在边都已被探寻过，搜索将回溯到发现节点V的那条边的起始节点，该过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个过程反复进行直到所有节点都被访问为止。在本题中，DFS用于搜索和标记相连的陆地。

广度优先搜索：也就是Breadth First Search，简称为BFS，这也是一种用于遍历或搜索树或图的算法。首先，它从根节点开始，访问所有与根节点相邻的节点。然后，扩展到下一层邻接节点，直到找到目标节点或者遍历完整棵树或图。

二维数组和矩阵操作：本题给出的地图是一个二维网格，需要使用二维数组来进行表示和操作。

边界条件判断：在搜索过程中文章来源地址https://www.toymoban.com/news/detail-799778.html

到了这里，关于C++面试宝典第20题：计算岛屿数量的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！