827.Making A Large Island

BFS/DFS + MATRIX

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: 3
Explanation: 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: 4
Explanation: 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: 4
Explanation: 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.

解题思路

这个问题可以分为两个主要步骤：

1. 识别并标记所有现有岛屿：使用DFS或BFS遍历矩阵，找到所有岛屿，并为每个岛屿分配一个唯一标识符，同时记录每个岛屿的面积。

2. 寻找最佳填海位置：对于每个 0，检查其四周的岛屿标识符，计算将这些岛屿连接起来后的总面积（注意去重），找出能形成最大岛屿的 0。

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n,m = len(grid), len(grid[0])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        # calculate all areas and set grid[x][y] with id(auto-increase, from 2)
        areaid = 2
        id2size = {}
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    curarea = 0
                    queue = [(i, j)]
                    grid[i][j] = areaid
                    while queue:
                        x, y = queue.pop()
                        curarea += 1
                        
                        for dx, dy in directions:
                            nx, ny = x + dx, y + dy
                            if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1:
                                grid[nx][ny] = areaid
                                queue.append((nx, ny))

                    id2size[areaid] = curarea
                    areaid += 1
        if not id2size:
            return 1 if n > 0 else 0
        res = max(id2size.values())
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 0:
                    neighbors = set()
                    for dx, dy in directions:
                        nx, ny = i + dx, j + dy
                        if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] > 1:
                            neighbors.add(grid[nx][ny])
                    cursum = 1+ sum(id2size[areaid] for areaid in neighbors)
                    res = max(res, cursum)
        return res