第73期-基础算法：广度优先搜索 岛屿的最大面积

Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。

1 问题描述

给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。

示例 1:

输入: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出: 6
解释: 答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

示例 2:

输入: grid = [[0,0,0,0,0,0,0,0]]
输出: 0

初始代码

from typing import List
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        #在此之间填写代码

print(Solution().maxAreaOfIsland([[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]))
print(Solution().maxAreaOfIsland([[0,0,0,0,0,0,0,0]]))

2 解题思路

• 标签：广度优先搜索 / 深度优先搜索
• 我们想知道网格中每个连通形状的面积，然后取最大值。
• 如果我们在一个土地上，以 44 个方向探索与之相连的每一个土地（以及与这些土地相连的土地），那么探索过的土地总数将是该连通形状的面积。
• 为了确保每个土地访问不超过一次，我们每次经过一块土地时，将这块土地的值置为 00。这样我们就不会多次访问同一土地。

3 解题方法

from typing import List
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        t=0
        m,n=len(grid),len(grid[0])
        queue=[]
        dir=[(1,0),(0,1),(-1,0),(0,-1)]
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1 :
                    grid[i][j]=0
                    t1=1
                    queue.append((i,j))
                    while queue:
                        cur=queue.pop(0)
                        for k in dir:
                            x,y=cur[0]+k[0],cur[1]+k[1]
                            if 0<=x<m and 0<=y<n and grid[x][y]==1:
                                grid[x][y]=0
                                t1+=1
                                queue.append((x,y))
                    if t1>t:t=t1
        return t

print(Solution().maxAreaOfIsland([[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]))
print(Solution().maxAreaOfIsland([[0,0,0,0,0,0,0,0]]))

第1-3，25-26行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑
第4行： 定义变量a为0，用于存放岛屿面积的最大值
第5行： 定义变量m，n用于存放整个海面的横竖长度和宽度
第6行： 定义列表queue用于存放接下来需要遍历的坐标
第7行： 定义列表dir用于存放四个方向
第8-9行： 使用for循环遍历矩阵中的每个点
第10行： 判断该点是否是岛屿，是则进行之后的操作
第11行： 将该岛屿数值赋值为0，避免之后再次遍历
第12行： 定义变量t1用于记录当前岛屿的面积
第13行： 在列表queue中存放当前岛屿的坐标
第14行： 当列表queue不为空时，执行接下来的循环
第15行： 在queue中删除第一个元素并将其赋值给cur
第16行： 使用for循环遍历上下左右四个方向
第16行： 定义变量x，y用于存放该方向的横竖坐标
第16行： 判断该点横竖坐标是否在矩阵内且该点是否为岛屿
第16行： 若满足条件，则先将该岛屿记录为0
第16行： 岛屿面积加一
第16行： 在queue队列中加如带点坐标，用于之后该点扩散
第16行： 该岛屿计算完成之后，若面积大于当前面积最大值，则赋值最大值给t
第16行： 全部点都遍历完成之后，返回最大值给函数

代码运行结果为：

算法讲解

这里用到了基础算法：广度优先搜索，简单讲解下这个算法：
广度优先搜索
广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。

树的广度优先遍历

图的广度优先遍历

树与图

4 视频解析

高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码