您的位置: 首页 > 文章 > 力扣小白刷题之200题岛屿数量 力扣小白刷题之200题岛屿数量 分类: 文章 • 2024-03-19 09:31:46 题目描述 由‘1’和‘0’组成的网格,计算网格中岛屿的数量 思路 深度优先搜索 将二维网格看成一个无向图,竖直或水平相邻的1之间有边相连。 遍历图,如果一个位置为 1,则以其为起始节点开始进行DFS,在深搜过程中,每个搜索到的 1 都会被标记为 0. 最终的岛屿数量就是DFS的次数 代码 时间复杂度: O(m * n) ,m为行数,n为列数空间复杂度: O(m * n) ,在最坏的情况下,整个网格均为陆地,DFS的深度达到 m * n。