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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
# 827. Making A Large Island
"""
you are given an 'm x n' binary matrix 'grid'. you are allowed to change at
most one 0 to be 1. return size of the largest island in 'grid' after
applying this operation. an island is a 4-directionally connected group of
1's.
"""
class Solution(object):
def largestIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
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, idx):
res = 0
grid[x][y] = idx
for i, j in move(x, y):
if grid[i][j] == 1:
res += dfs(i, j, idx)
return res + 1
idx, areas = 2, {0: 0}
for x in range(n):
for y in range(n):
if grid[x][y] == 1:
areas[idx] = dfs(x, y, idx)
idx += 1
ans = max(areas.values())
for x in range(n):
for y in range(n):
if grid[x][y] == 0:
valid = set(grid[i][j] for i, j in move(x, y))
ans = max(ans, sum(areas[idx] for idx in valid) + 1)
return ans
if __name__ == "__main__":
obj = Solution()
print(obj.largestIsland(grid=[[1, 0], [0, 1]]))
print(obj.largestIsland(grid=[[1, 1], [1, 0]]))
print(obj.largestIsland(grid=[[1, 1], [1, 1]]))
|