今日题目

https://leetcode.com/problems/making-a-large-island/description/

思路

本题要求将一个 0 翻转为 1，以求得最大的连通区域。如果我们能事先计算出网格中每个 0 的四个方向上各连通块的大小，那么只需将它们相加即可得到答案。

方法

首先计算每个连通块的大小，并为每个连通块打上标签，避免重复累加同一个连通块。

然后遍历所有的 0，将其翻转后的结果即为其四个方向上不重复连通块的大小之和。

复杂度

  • 时间复杂度：$O(N^2)$

  • 空间复杂度：$O(N^2)$

代码

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        islandCount = [0,0]
        dx = [0,0,1,-1]
        dy = [1,-1,0,0]
        n = len(grid)
        m = len(grid[0])
        
        def dfs(x, y, cnt):
            grid[x][y] = cnt
            islandCount[cnt] += 1
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= n or ny >= m or grid[nx][ny] != 1:
                    continue
                
                dfs(nx, ny, cnt)

                
        cnt = 1
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    cnt += 1
                    islandCount.append(0)
                    dfs(i, j, cnt)
        
        ans = max(islandCount)

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0:
                    tmp = 1
                    vis = set([])
                    for k in range(4):
                        nx = i + dx[k]
                        ny = j + dy[k] 
                        if nx < 0 or ny < 0 or nx >= n or ny >= m or grid[nx][ny] in vis:
                            continue
                        tmp += islandCount[grid[nx][ny]]
                        vis.add(grid[nx][ny])
                    
                    ans = max(ans, tmp)

        return ans