代码随想录算法训练营第五十一天|200. 岛屿数量|695.岛屿的最大面积

200. 岛屿数量

题目描述：

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述：

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述：

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

---

DFS

class Solution:

    def numIslands(self, grid: List[List[str]]) -> int:

        def dfs(i,j,grid):

            if not 0<=i<len(grid) or not 0<=j<len(grid[0]) or grid[i][j]=='0':

                #定位从0到len-1

                #矩阵中是文本格式

                return

            grid[i][j]='0'

            dfs(i+1,j,grid)

            dfs(i-1,j,grid)

            dfs(i,j-1,grid)

            dfs(i,j+1,grid)

        count=0

        for i in range(len(grid)):

            for j in range(len(grid[0])):

                if grid[i][j]=='1':

                    dfs(i,j,grid)

                    count+=1

        return count

                    

---

BFS

class Solution:

    def numIslands(self, grid: List[List[str]]) -> int:

        def bfs(i,j,grid):

            queue=[[i,j]]

            while queue:

                [i,j]=queue.pop(-1)

                if 0<=i<len(grid) and 0<=j<len(grid[0]) and grid[i][j]=='1':

                    grid[i][j]='0'

                    queue.append([i-1,j])

                    queue.append([i,j-1])

                    queue.append([i+1,j])

                    queue.append([i,j+1])

        count=0

        for i in range(len(grid)):

            for j in range(len(grid[0])):

                if grid[i][j]=='0':

                    continue

                bfs(i,j,grid)

                count+=1

        return count

---

 在 Python 里，像非零数字、非空字符串、非空列表等都是真值，而  0 、 "" （空字符串）、 [] （空列表）、 False  等是假值。

---

 695.岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

---

DFS

class Solution:

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

        m=len(grid)

        n=len(grid[0])

        def dfs(i,j,grid):

            if 0<=i<m and 0<=j<n and grid[i][j]:

                grid[i][j]=0

                return 1+dfs(i-1,j,grid)+dfs(i+1,j,grid)+dfs(i,j+1,grid)+dfs(i,j-1,grid)

            return 0

        fres=0

        for i in range(m):

            for j in range(n):

                if grid[i][j]:

                    fres=max(dfs(i,j,grid),fres)

        return fres                         

---

BFS

from typing import List

class Solution:

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

        m,n=len(grid),len(grid[0])

        def bfs(resi,resj,grid):

            queue=[(resi,resj)]

            res=1

            grid[resi][resj]=0

            while queue:

                resi,resj=queue.pop(0)

                for a,b in ((0,1),(1,0),(0,-1),(-1,0)):

                    ri=resi+a

                    rj=resj+b

                    if 0<=ri<m and 0<=rj<n and grid[ri][rj]:

#2. 访问越界检查：在  bfs  函数中，虽然对  ri  和  rj  进行了边界检查（ 0 <= ri < m and 0 <= rj < n ），但在访问  grid[ri][rj]  时，如果  ri  或  rj  越界，仍然会引发  IndexError 。为了避免这种情况，应该先检查边界条件，再访问  grid[ri][rj] 。

                        res+=1

                        queue.append((ri,rj))

                        grid[ri][rj]=0

            return res 

        fres=0

        for i in range(m):

            for j in range(n):

                if grid[i][j]:

                    fres=max(fres,bfs(i,j,grid))

        return fres