[leetcode/lintcode 题解] 阿里面试题：生成更大的陆地

描述
在一个0和1的2D网格中，我们最多将一个0改为1。
之后，最大岛屿的大小是多少？ （一个岛是四个方向上互相连接的一组1）。

• 1 <= grid.length = grid[0] .length <= 50。
• 0 <= grid [i] [j] <= 1。

在线评测地址：领扣题库官网

样例1
输入：[[1,0]，[0,1]]
输出：3

解释：
将0改为1并连接两个1，然后我们得到一个面积= 3的岛。

        

          
        
        
        

          

          AI 代码解读
        
      
      

样例 2:
输入：[[1,1]，[1,0]]
输出：4

解释：
将0更改为1并使岛变大，只有一个面积= 4的岛。

        

          
        
        
        

          

          AI 代码解读
        
      
      

样例 3:
输入：[[1,1]，[1,1]]
输出：4

解释：
不能将任何0更改为1，只有一个面积= 4的岛。

        

          
        
        
        

          

          AI 代码解读
        
      
      

解题思路
将位置0变成1，然后在该位置进行深搜，另外用一个数组作为标记位, 深搜的过程中统计岛的面积。
源代码

class Solution:
    def largestIsland(self, grid):
        N = len(grid)
        def move(x, y):
            for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                if 0 <= x + i < N and 0 <= y + j < N:
                    yield x + i, y + j
        def dfs(x, y, index):
            area = 0
            grid[x][y] = index
            for i, j in move(x, y):
                if grid[i][j] == 1:
                    area += dfs(i, j, index)
            return area + 1
        index = 2
        area = {}
        for x in range(N):
            for y in range(N):
                if grid[x][y] == 1:
                    area[index] = dfs(x, y, index)
                    index += 1
        res = max(area.values() or [0])
        for x in range(N):
            for y in range(N):
                if grid[x][y] == 0:
                    possible = set(grid[i][j] for i, j in move(x, y) if grid[i][j] > 1)
                    res = max(res, sum(area[index] for index in possible) + 1)
        return res

        

          
        
        
        

          

          AI 代码解读
        
      
      

更多题解参考：九章官网solution