复制
收藏
提问
简洁
给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。
3月前
全网
文档
学术
百科
知识库
回答简洁模式
深入研究一些
要解决这个问题,我们可以使用深度优先搜索(DFS)算法。基本思路是遍历整个二维网格,当遇到一个值为'1'的格子时,就认为找到了一个岛屿的起点,然后从这个点开始进行深度优先搜索,直到所有相邻的陆地都被访问过。在搜索过程中,将访问过的陆地标记为已访问(通常可以将其改为'0'),以避免重复计数。每完成一次DFS,就表示找到了一个岛屿,岛屿数量加一。重复这个过程,直到整个网格都被遍历完毕。
以下是具体的算法步骤:
- 初始化岛屿数量为0。
- 遍历整个二维网格的每一个格子。
- 当遇到值为'1'的格子时,执行深度优先搜索(DFS)。
- 在DFS中,将当前访问的陆地格子标记为已访问(例如,将其改为'0')。
- 同时,继续搜索当前格子的上下左右四个方向的相邻格子,如果相邻格子也是'1',则继续DFS。
- 每次完成DFS后,岛屿数量加一。
- 重复步骤2-6,直到所有格子都被遍历过。
你觉得结果怎么样?