diff options
Diffstat (limited to 'making_large_island.py')
-rw-r--r-- | making_large_island.py | 51 |
1 files changed, 51 insertions, 0 deletions
diff --git a/making_large_island.py b/making_large_island.py new file mode 100644 index 0000000..24e0845 --- /dev/null +++ b/making_large_island.py @@ -0,0 +1,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]])) |