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: 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 = 4.
Example 3:
Input: [[1, 1], [1, 1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.
Notes:
1 <= grid.length = grid[0].length <= 50.
0 <= grid[i][j] <= 1.
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        parent = {}
        nums = collections.defaultdict(int)
        visited = set()
        res = 1
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1 and (i, j) not in parent:
                    parent[(i, j)] = (i, j)
                    stack = [(i, j)]
                    while stack:
                        x, y = stack.pop()
                        nums[(i, j)] += 1
                        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
                        for direction in directions:
                            dx, dy = direction
                            if self.is_valid(grid, (x + dx, y + dy), parent):
                                parent[(x+dx, y+dy)] = (i, j)
                                stack.append((x + dx, y + dy))
        
        for v in list(nums.values()):
            res = max(res, v)
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    candidates = []
                    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
                    for direction in directions:
                        dx, dy = direction
                        if i + dx < 0 or i + dx >= len(grid) or j + dy < 0 or j + dy >= len(grid[0]):
                            continue
                        # if (i+dx, j+dy) in visited:
                        #     continue
                        if grid[i+dx][j+dy] == 1:
                            continue
                        visited.add((i+dx, j+dy))
                        res = max(res, nums[parent[i, j]] + 1)
                        extra = 1
                        temp_visited = set()
                        for second_direction in directions:
                            ddx, ddy = second_direction
                            if i + dx + ddx < 0 or i + dx + ddx >=len(grid) or j + dy + ddy < 0 or j + dy + ddy >= len(grid[0]):
                                continue
                            if grid[i+dx+ddx][j+dy+ddy] == 0:
                                continue
                            if parent[(i+dx+ddx, j+dy+ddy)] == parent[(i, j)]:
                                continue
                            if parent[(i+dx+ddx, j+dy+ddy)] in temp_visited:
                                continue
                            else:
                                extra += nums[parent[i+dx+ddx, j+dy+ddy]]
                                temp_visited.add(parent[(i+dx+ddx, j+dy+ddy)])
                        
                        res = max(res, nums[parent[i, j]] + extra)
        
        return res
        
        
    def is_valid(self, grid, pos, parent):
        x, y = pos
        if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):
            return False
        if (x, y) in parent:
            return False
        if grid[x][y] == 0:
            return False
        
        return True
                    

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        parent = {}
        nums = collections.defaultdict(int)
        visited = set()
        res = 1
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1 and (i, j) not in parent:
                    parent[(i, j)] = (i, j)
                    stack = [(i, j)]
                    while stack:
                        x, y = stack.pop()
                        nums[(i, j)] += 1
                        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
                        for direction in directions:
                            dx, dy = direction
                            if self.is_valid(grid, (x + dx, y + dy), parent):
                                parent[(x+dx, y+dy)] = (i, j)
                                stack.append((x + dx, y + dy))
        
        for v in list(nums.values()):
            res = max(res, v)
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    candidates = []
                    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
                    for direction in directions:
                        dx, dy = direction
                        if i + dx < 0 or i + dx >= len(grid) or j + dy < 0 or j + dy >= len(grid[0]):
                            continue
                        # if (i+dx, j+dy) in visited:
                        #     continue
                        if grid[i+dx][j+dy] == 1:
                            continue
                        visited.add((i+dx, j+dy))
                        res = max(res, nums[parent[i, j]] + 1)
                        extra = 1
                        temp_visited = set()
                        for second_direction in directions:
                            ddx, ddy = second_direction
                            if i + dx + ddx < 0 or i + dx + ddx >=len(grid) or j + dy + ddy < 0 or j + dy + ddy >= len(grid[0]):
                                continue
                            if grid[i+dx+ddx][j+dy+ddy] == 0:
                                continue
                            if parent[(i+dx+ddx, j+dy+ddy)] == parent[(i, j)]:
                                continue
                            if parent[(i+dx+ddx, j+dy+ddy)] in temp_visited:
                                continue
                            else:
                                extra += nums[parent[i+dx+ddx, j+dy+ddy]]
                                temp_visited.add(parent[(i+dx+ddx, j+dy+ddy)])
                        
                        res = max(res, nums[parent[i, j]] + extra)
        
        return res
        
        
    def is_valid(self, grid, pos, parent):
        x, y = pos
        if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):
            return False
        if (x, y) in parent:
            return False
        if grid[x][y] == 0:
            return False
        
        return True
                    
