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

樣例 2:
輸入：[[1,1]，[1,0]]
輸出：4

解釋：
将0更改為1并使島變大，隻有一個面積= 4的島。           

樣例 3:
輸入：[[1,1]，[1,1]]
輸出：4

解釋：
不能将任何0更改為1，隻有一個面積= 4的島。           

解題思路

将位置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
           

更多題解參考：

九章官網solution