動機

python的主場來啦

Problem

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

Return the size of the largest island in grid after applying this operation.

An island is a 4-directionally connected group of 1s.

 

Example 1:

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

Example 3:

Input: grid = [[1,1],[1,1]]Output: 4Explanation: Can't change any 0 to 1, only one island with area = 4.

 

Constraints:

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 500
  • grid[i][j] is either 0 or 1.

Sol

用dfs找面積，之後用dfs設定面積

在設定面積時會碰到邊界，就可以用list去放現在的面積，但下一個遇到list也可以放

最後就是數list的總和

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        def area(i,j):
            if 0<= i < len(grid) and 0 <= j < len(grid[i]) and grid[i][j] == 1:
                grid[i][j] = -1
                dirs = [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]
                return sum([area(x,y) for (x,y) in dirs])+1
            else:
                return 0
        def setArea(i,j,n,seen):
            if 0<= i < len(grid) and 0 <= j < len(grid[i]):
                if grid[i][j] == -1:
                    grid[i][j] = n
                    dirs = [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]
                    [setArea(x,y,n,seen) for (x,y) in dirs]
                elif grid[i][j] == 0:
                    grid[i][j] = [n]
                    seen.add((i,j))
                elif isinstance(grid[i][j], list) and (i,j) not in seen:
                    seen.add((i,j))
                    grid[i][j].append(n)
        
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == 1:
                    setArea(i,j,area(i,j)+1,set()) # to distigish 1 from area 1
        
        ret = 1
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if isinstance(grid[i][j], list):
                    ret = max(ret, 1+sum(grid[i][j])-len(grid[i][j]))
                else:
                    ret = max(ret, grid[i][j]-1)
        return ret