Q695-岛屿的最大面积-中等-深度/宽度优先搜索

695. 岛屿的最大面积

Question

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

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

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

Example 1:

[[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 。

Example 2:

[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵, 返回 0。

Note:

给定的矩阵grid 的长度和宽度都不超过 50。

Approach 1: 深度优先搜索+递归

这个思路比较好理解，DFS+递归可以按照这个步骤思考

计算行数，列数
遍历二维数组，计算当前“岛屿”面积，并与最大面积对比取最大值
- 在DFS函数中计算当前岛屿的面积
- 先判断位置是否合法（r and c）
- 如果当前位置是1，那就置0，避免重复，在返回结果递归DFS，检测周围是否是岛屿

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def DFS(grid,ci,cj):
            if 0<=ci and ci<r and 0<=cj and cj<c and grid[ci][cj] == 1:
                grid[ci][cj] = 0
                return 1 + DFS(grid,ci-1,cj) + DFS(grid,ci+1,cj) + DFS(grid,ci,cj-1) + DFS(grid,ci,cj+1)
            else:
                return 0

        r , c = len(grid),len(grid[0])
        fin_res = 0
        for i in range(r):
            for j in range(c):
                fin_res = max(DFS(grid,i,j),fin_res)
        return fin_res

复杂度分析

时间复杂度：。其中 R 是给定网格中的行数，C 是列数。我们访问每个网格最多一次。
空间复杂度：，递归的深度最大可能是整个网格的大小，因此最大可能使用的栈空间。

Approach 2: 广度优先搜索

广度优先的写法需要建立一个队列que，记录当前遍历到的结点，结合while que进行遍历

遍历每个元素，判断是否是1，是则放入que
对每个放入que的元素遍历几种移动情况，满足条件的元素置零后放入que，继续遍历

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        r , c = len(grid) , len(grid[0])
        total_res = 0
        for i in range(r):
            for j in range(c):
                ans = 0
                que = []
                if grid[i][j] == 1:
                    grid[i][j] = 0
                    ans += 1
                    que.append((i,j))
                    while que:
                        cur_r,cur_c = que.pop(0)
                        for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                            temp_r , temp_c = cur_r + dr , cur_c + dc
                            if 0<=temp_r and temp_r<r and 0<=temp_c and temp_c<c and grid[temp_r][temp_c] == 1:
                                grid[temp_r][temp_c] = 0
                                ans += 1
                                que.append((temp_r,temp_c))
                total_res = max(total_res,ans)
        return total_res

另一种写法，每次从队首取出土地，并将接下来想要遍历的土地放在队尾，就实现了广度优先搜索算法。

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        for i, l in enumerate(grid):
            for j, n in enumerate(l):
                cur = 0
                q = collections.deque([(i, j)])
                while q:
                    cur_i, cur_j = q.popleft()
                    if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:
                        continue
                    cur += 1
                    grid[cur_i][cur_j] = 0
                    for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                        next_i, next_j = cur_i + di, cur_j + dj
                        q.append((next_i, next_j))
                ans = max(ans, cur)
        return ans

复杂度分析

时间复杂度：。其中 R 是给定网格中的行数，C 是列数。我们访问每个网格最多一次。
空间复杂度：，队列中最多会存放所有的土地，土地的数量最多为块，因此使用的空间为。