题目一:小明想知道哪个岛是最大的岛屿,请你用深度优先遍历算法来帮助他。如图所示,为了方便计算,我们使用一个二维数组来表示一片海域,用0表示水面,用1表示陆地,我们的任务是找出其中最大的岛屿。注意,岛屿是指上下左右四个方向相连接的陆地。
时间: 2024-05-03 22:16:59 浏览: 26
题目描述:给定一个二维数组,其中0表示水,1表示陆地,请找出其中最大的岛屿。
算法思路:使用深度优先遍历算法,从每一个陆地点开始向四周扩散,直到无法继续扩散为止,计算扩散过程中陆地的数量,找出最大的岛屿。
具体实现:
```python
def dfs(grid, i, j):
"""
深度优先遍历算法
"""
# 如果当前点不为1,直接返回0
if not grid[i][j]:
return 0
# 当前点为1,将其标记为0
grid[i][j] = 0
# 向四周扩散
count = 1
if i > 0:
count += dfs(grid, i-1, j)
if i < len(grid) - 1:
count += dfs(grid, i+1, j)
if j > 0:
count += dfs(grid, i, j-1)
if j < len(grid[0]) - 1:
count += dfs(grid, i, j+1)
return count
def maxAreaOfIsland(grid):
"""
主函数,遍历每一个陆地点,找出最大的岛屿
"""
max_area = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]:
area = dfs(grid, i, j)
max_area = max(max_area, area)
return max_area
```
使用样例:
```python
grid = [[1, 1, 0, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 1, 1],
[0, 0, 0, 1, 1]]
print(maxAreaOfIsland(grid)) # 输出6
```
解释:上图中,最大的岛屿为由4个1组成的岛屿,其大小为6。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)