## 题目描述：

LeetCode 827. Making A Large Island

In a 2D grid of `0`s and `1`s, 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 `1`s).

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: Can't change any 0 to 1, only one island with area = 1.```

Notes:

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

Notes:

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

## 解题思路：

```利用辅助二维数组mark记录grid中的元素属于哪个岛屿

## Python代码：

``````class Solution(object):
def largestIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
h, w = len(grid), len(grid[0])
mark = [[0] * w for x in range(h)]

def neighbors(x, y):
for dx, dy in zip((1, 0, -1, 0), (0, 1, 0, -1)):
nx, ny = x + dx, y + dy
if 0 <= nx < h and 0 <= ny < w and grid[nx][ny]:
yield (nx, ny)

def calcAndMarkArea(sx, sy, mk):
q = [(sx, sy)]
vset = set(q)
ans = 0
while q:
x, y = q.pop(0)
ans += 1
for nx, ny in neighbors(x, y):
if (nx, ny) not in vset:
q.append((nx, ny))
for x, y in vset:
mark[x][y] = mk
grid[x][y] = ans
return ans

maxArea = 0
mk = 0
for x in range(h):
for y in range(w):
if grid[x][y] and not mark[x][y]:
mk += 1
maxArea = max(calcAndMarkArea(x, y, mk), maxArea)

for x in range(h):
for y in range(w):
if grid[x][y] == 0:
area = 0
mkset = set()
for nx, ny in neighbors(x, y):
if mark[nx][ny] not in mkset:
area += grid[nx][ny]
maxArea = max(maxArea, area + 1)
return maxArea
``````

Pingbacks已关闭。