827最大人工岛

题目：在二维地图上， 0代表海洋， 1代表陆地，我们最多只能将一格 0 海洋变成 1变成陆地。进行填海之后，地图上最大的岛屿面积是多少？（上、下、左、右四个方向相连的 1 可形成岛屿）
链接：https://leetcode-cn.com/problems/making-a-large-island

法一：自己的代码

思路：两次遍历，第一次记录面积和类别，第二次求最大值

from typing import List
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        r_length = len(grid)
        c_length = len(grid[0])
        memo = {}
        dirctions = [(0,1), (0,-1), (1,0), (-1,0)]
        cate = 1
        # 两次遍历，第一次遍历记录每个坐标所在的岛屿面积和岛屿类别
        for r in range(r_length):
            for c in range(c_length):
                if (r,c) in memo:
                    continue
                elif grid[r][c] == 1:
                    cache = []
                    a = []
                    cache.append((r,c))
                    a.append((r,c))
                    while a:
                        p,q = a.pop(0)
                        for m,n in dirctions:
                            x = p + m
                            y = q + n
                            if 0 <= x < r_length and 0 <= y < c_length and grid[x][y] == 1 and (x,y) not in cache:
                                a.append((x,y))
                                cache.append((x,y))
                    l = len(cache)
                    for i in cache:
                        memo[i] = (l,cate)
                    cate += 1
                else:
                    memo[(r,c)] = (0,0)
        res = 1
        # t用于识别是不是都是1
        t = 1
        # 第二次遍历为0的坐标，求最大值
        for r in range(r_length):
            for c in range(c_length):
                if memo[(r,c)][0] == 0:
                    t += 1
                    a = []
                    for m,n in dirctions:
                        x = r + m
                        y = c + n
                        if 0 <= x < r_length and 0 <= y < c_length:
                            a.append(memo[(x,y)])
                    a = set(a)
                    b = 0
                    for i in a:
                        b = b + i[0]
                    res = max(res, b+1)
        return res if t != 1 else r_length * c_length

法二：官方代码

思路：写法更加简洁，关键是生成了一个字典，键是不同的岛屿，值是岛屿的面积，并且在dfs的时候，把岛屿的值也都修改成了其编号，使得在后续遍历为0的元素时，更加方便，此外遍历岛屿采用递归的dfs也比迭代更简洁。

知识点：字典和集合的生成方式相同，都是{}，只不过当括号内全是键值对时，就是字典，当全是单个的字符或者字符串时，就是集合，

学会使用yield写迭代器，在for循环的时候很方便，写成函数，代码容易复用，

class Solution(object):
    def largestIsland(self, grid):
        N = len(grid)
        def neighbors(r, c):
            for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
                if 0 <= nr < N and 0 <= nc < N:
                    yield nr, nc
        # 返回的是岛屿的面积
        def dfs(r, c, index):
            ans = 1
            # 注意每个等于1的grid[r][c]遍历前都被改变了，
            grid[r][c] = index
            # 这里的neighbors()函数可以看做一个迭代器，好处是每次返回的坐标一定是在数组内的，可以直接判断
            for nr, nc in neighbors(r, c):
                # 已经遍历过的一定不是1，所以不会重复遍历
                if grid[nr][nc] == 1:
                    ans += dfs(nr, nc, index)
            return ans
        area = {}
        index = 2
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    # 字典中的键是岛屿的编号，值是岛屿的面积
                    area[index] = dfs(r, c, index)
                    index += 1
        ans = max(area.values() or [0])
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 0:
                    # 生成grid[r][c]周围所有的不同编号
                    seen = {grid[nr][nc] for nr, nc in neighbors(r, c) if grid[nr][nc] > 1}
                    # 求和，1是grid[r][c]本身
                    ans = max(ans, 1 + sum(area[i] for i in seen))
        return ans
if __name__ == '__main__':
    solution = Solution()
    # result = solution.largestIsland([[1,1],[1,0]])
    result = solution.largestIsland([[0,1],[1,1]])
    print(result)

ttt