Leetcode_827_Making_A_Large_Island

发表于 |

In a 2D grid of 0s and 1s, we change at most one 0 to a 1.

After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).

Example 1:
Input: [[1, 0], [0, 1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:
Input: [[1, 1], [1, 0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 1.

Example 3:
Input: [[1,1],[1,1]]
Output: 4
Explanation: 4

Notes:
1 <= grid.length = grid[0].length <= 50.
0 <= grid[i][j] <= 1.

分析：
这道题意思就是把连续的1认为是一块地,现在可以将某个0改成1，使连续的1最多，并求出对应的数量。
先看一下变量的取值，长宽都是50，则最多2500个元素，这告诉我们n^2复杂度是可以的

思路：
我们给每块地进行编号，然后记录下这块地的大小，最后找0的时候将0周边不同地的面积相加最大的就是结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def largestIsland(grid):
    directions = ((1,0),(0,1),(-1,0),(0,-1))
    area = [0,0]
    index = 2 # grid中包含0，1，所以地的编号从2开始必不会重复
    n = len(grid)
    # 用dfs计算一块地的面积，并修改grid
    def dfs(i,j,index):
        res = 1
        grid[i][j] = index
        for x,y in directions:
            if 0<=i+x<n and 0<=j+y<n:
                if grid[i+x][j+y] == 1:
                    res += dfs(i+x,j+y,index)
        return res

    # 用area数组记录对应地的面积
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                area.append(dfs(i,j,index))
                index += 1

    res = 0
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 0:
                s = set()
                for x,y in directions:
                    if 0<=i+x<n and 0<=j+y<n and grid[i+x][j+y]>1:
                        s.add(grid[i+x][j+y])
                res = max(res,sum(area[i] for i in s)+1)
    # 如果grid中全为1，上一个循环中的判断就进不去，res就为0，此时结果应该为grid的面积
    return res or n**2

"difficulty:hard
63/63 test cases passed
runtime: 127ms"