难度: Hard
给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后，grid 中最大的岛屿面积是多少？
岛屿 由一组上、下、左、右四个方向相连的 1 形成。
示例 1:
输入: grid = [[1, 0], [0, 1]] 输出: 3 解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
示例 2:
输入: grid = [[1, 1], [1, 0]] 输出: 4 解释: 将一格0变成1，岛屿的面积扩大为 4。
示例 3:
输入: grid = [[1, 1], [1, 1]] 输出: 4 解释: 没有0可以让我们变成1，面积依然为 4。
提示：
n == grid.lengthn == grid[i].length1 <= n <= 500grid[i][j] 为 0 或 1运行时间: 413 ms
内存: 27.6 MB
class Solution:
def largestIsland(self, grid: list[list]):
dum=1
dtom={0:0}
li=len(grid)
lj=len(grid[0])
def biaozhu(i,j):
if(i<0 or j<0 or i>=li or j>=lj):
return
elif grid[i][j]==1:
grid[i][j]=dum
dtom[dum]+=1
biaozhu(i+1,j)
biaozhu(i-1,j)
biaozhu(i,j+1)
biaozhu(i,j-1)
else:
return
for i in range(li):
for j in range(lj):
if grid[i][j]==1:
dum+=1
dtom[dum]=0
biaozhu(i,j)
if(dum==1):
return 1
elif dtom[2]==li*lj:
return dtom[2]
maxmian=0
def countmian(i,j):
tem=1
tlist=[]
if i+1<li:
tem+=dtom[grid[i+1][j]]
tlist.append(grid[i+1][j])
if i-1>=0 and not grid[i-1][j] in tlist:
tem+=dtom[grid[i-1][j]]
tlist.append(grid[i-1][j])
if j+1<lj and not grid[i][j+1] in tlist:
tem+=dtom[grid[i][j+1]]
tlist.append(grid[i][j+1])
if j-1>=0 and not grid[i][j-1] in tlist:
tem+=dtom[grid[i][j-1]]
return tem
for i in range(li):
for j in range(lj):
if grid[i][j]==0:
tem=countmian(i,j)
maxmian=tem if tem>maxmian else maxmian
return maxmian
这个题解采用了深度优先搜索（DFS）的思路。首先，遍历整个网格，对于每个值为1的格子，执行DFS遍历其连通的1，并标记为一个新的岛屿编号（dum），同时记录该岛屿的面积。接着，再次遍历网格，对于每个值为0的格子，计算若将其变为1后，能够连接到的岛屿的面积之和，更新最大面积。最后返回最大面积。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
class Solution:
def largestIsland(self, grid: list[list]):
dum=1
dtom={0:0} # 用于存储岛屿编号和对应的面积
li=len(grid)
lj=len(grid[0])
def biaozhu(i,j): # DFS遍历连通的1，并标记岛屿编号
if(i<0 or j<0 or i>=li or j>=lj):
return
elif grid[i][j]==1:
grid[i][j]=dum
dtom[dum]+=1
biaozhu(i+1,j)
biaozhu(i-1,j)
biaozhu(i,j+1)
biaozhu(i,j-1)
else:
return
for i in range(li): # 遍历网格，对每个值为1的格子执行DFS标记
for j in range(lj):
if grid[i][j]==1:
dum+=1
dtom[dum]=0
biaozhu(i,j)
if(dum==1): # 特殊情况处理
return 1
elif dtom[2]==li*lj:
return dtom[2]
maxmian=0
def countmian(i,j): # 统计将(i,j)变为1后，连接到的岛屿面积之和
tem=1
tlist=[]
if i+1<li:
tem+=dtom[grid[i+1][j]]
tlist.append(grid[i+1][j])
if i-1>=0 and not grid[i-1][j] in tlist:
tem+=dtom[grid[i-1][j]]
tlist.append(grid[i-1][j])
if j+1<lj and not grid[i][j+1] in tlist:
tem+=dtom[grid[i][j+1]]
tlist.append(grid[i][j+1])
if j-1>=0 and not grid[i][j-1] in tlist:
tem+=dtom[grid[i][j-1]]
return tem
for i in range(li): # 遍历网格，对每个值为0的格子，统计连接的岛屿面积之和，更新最大面积
for j in range(lj):
if grid[i][j]==0:
tem=countmian(i,j)
maxmian=tem if tem>maxmian else maxmian
return maxmian
在执行DFS时，将已访问的'1'改为岛屿编号'dum'而不是统一的其他标记（如-1或特定字符），可以在同一次遍历中同时完成标记和岛屿识别。这样可以避免后续再次遍历来确定不同岛屿的归属，提高效率。此外，这种方式可以直接利用岛屿编号来记录和查询每个岛屿的面积，简化数据结构和逻辑处理，尤其在处理复杂或大型网格时，可以有效地管理和更新岛屿相关信息。
题解中采用了一个列表`tlist`来避免重复计算相邻岛屿面积。每当计算一个0格子相邻的岛屿面积时，首先检查该岛屿编号是否已在`tlist`中记录。如果未记录，则将其面积加到总和中，并把这个编号添加到`tlist`中。这样可以确保即使0格子相邻四个方向为不同岛屿，每个岛屿的面积只被计算一次。
这两个检查处理了所有格子都是水（0）和所有格子都是陆地（1）的两种特殊情况。当'dum==1'时，表示没有任何岛屿被标记，即整个网格全是水，返回1因为可以将一个0转换为1形成一个大小为1的岛屿。当'dtom[2]==li*lj'时，表示唯一的岛屿编号为2且面积等于网格的总格数，此时整个网格全是陆地，所以返回这个陆地的面积。
题解中用的递归DFS确实可能在非常大的网格中引起栈溢出。为避免这种情况，可以使用迭代的DFS来代替递归DFS。在迭代的DFS中，可以使用一个显式的栈来模拟递归调用栈，这样可以更好地控制栈的大小和避免溢出。另外，也可以考虑使用广度优先搜索（BFS），它通常使用队列来实现，对于大规模数据也较为稳定。