827. Making A Large Island (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def largestIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        self.seen = set()
        
        def dfs(i, j):
            self.cur += 1
            self.seen.add((i, j))
            self.visited.add((i, j))
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n and (x, y) not in self.seen and grid[x][y] == 1:
                    dfs(x, y)
                    
        areas = [[(0, 0)] * m for _ in range(n)]
        result = 1
        mark = 0
        for i in range(m):
            for j in range(n):
                if (i, j) not in self.seen and grid[i][j] == 1:
                    self.cur = 0
                    self.visited = set()
                    dfs(i, j)
                    for x, y in self.visited:
                        areas[x][y] = (self.cur, mark)
                    mark += 1
                    result = max(result, self.cur)
                    
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    temp = []
                    s = set()
                    for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                        x, y = i + dx, j + dy
                        if 0 <= x < m and 0 <= y < n and areas[x][y][0] > 0:
                            a, b = areas[x][y]
                            if b not in s:
                                s.add(b)
                                temp.append(a)
                    result = max(result, sum(temp) + 1)
        return result