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: 3Explanation: 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: 4Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 1.

Example 3:

Input: [[1, 1], [1, 1]]Output: 4Explanation: 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.

 

这个题目我只能想到naive的做法, T: O((m*n)^2), 就是对每个 grid[i][j] == 0 的元素, 将其换为1, 然后用BFS来计算size, 一直循环, 找最大值, 如果没有0 的话返回m*n.

然后参考了这个. 思路就是最开始将grid扫一遍, 每次如果grid[i][j] == 1, 将该点及所有跟它相连的为1 的点, 标记为color, 然后将各个不同的island tag为不同颜色, 并且用d2来存color和这个color的island 的size, 思路和做法跟一样, 只是需要标记color. 

这样之后可以得到如上图所示的结果, 然后再将grid扫一遍, 这一次是针对 grid[i][j] == 0 的元素, 然后看四个邻居是否为1, 如果是的话将它的size加入到temp里面,只是要注意的是有可能同样颜色的可以是多个neig, 所以要用set来排除已经加入同样颜色的size了, 最后返回最大值即可.

 

1. Constraints

1) size of grid, [1*1] ~ [50*50]

2) element will only be 0 or 1

 

2. Ideas 

DFS/BFS    用BFS,      T: O(m*n)     S: O(m*n)

 

3. Code

1 class Solution: 2     def largestIsland(self, grid): 3         def bfs(grid, d1, i, j, d2, dirs, color): 4             lr, lc, d1[(i, j)], queue, size = len(grid), len(grid[0]), color, collections.deque([(i,j)]), 1 5      6             while queue: 7                 pr, pc = queue.popleft() 8                 for c1, c2 in dirs: 9                     nr, nc = c1 + pr , c2 + pc10                     if 0 <= nr < lr and 0 <= nc < lc and (nr, nc) not in d1:11                         d1[(nr, nc)] = color12                         queue.append((nr, nc))13                         size += 114             d2[color] = size15         d1, d2, lr, lc , dirs, temp, color = {},{}, len(grid), len(grid[0]), [(0,1), (0,-1), (1, 0), (-1,0)], -1, 116         for i in range(lr):17             for j in range(lc):18                 if grid[i][j] == 1 and (i,j) not in d1:19                     color += 120                     bfs(grid, d1, i, j, d2, dirs, color)21 22         for i in range(lr):23             for j in range(lc):24                 if grid[i][j] == 0:25                     colors = set()26                     for c1, c2 in dirs:27                         nr, nc = i+ c1, j + c228                         if 0 <= nr < lr and 0 <= nc < lc and grid[nr][nc] == 1:29                             colors.add(d1[nr][nc])30                     s = sum(d2[color] for color in colors) + 131                     temp = s if temp == -1 else max(temp, s)32         return temp if temp != -1 else lr*lc