题目
给你一个大小为 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。
解题
方法一：dfs+map+枚举变化点
通过map记录每个岛屿对应的面积
通过不同值去标记不同的岛屿。
然后遍历矩阵，尝试让0变成1，然后查看最大面积
class Solution { public: vector<vector<int>> dirs={{-1,0},{1,0},{0,-1},{0,1}}; void dfs(unordered_map<int,int>& mp,vector<vector<int>>& grid,int id,int x,int y,int& area){ grid[x][y]=id; area++; for(vector<int>& dir:dirs){ int nx=x+dir[0]; int ny=y+dir[1]; if(nx<0||nx>=grid.size()||ny<0||ny>=grid.size()||grid[nx][ny]!=1) continue; dfs(mp,grid,id,nx,ny,area); } } int largestIsland(vector<vector<int>>& grid) { int n=grid.size(); int id=-1; unordered_map<int,int> mp; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(grid[i][j]!=1) continue; int area=0; dfs(mp,grid,id,i,j,area); mp[id]=area; id--; } } int res=0; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(grid[i][j]==0){ unordered_set<int> set; int cur=1; for(vector<int>& dir:dirs){ int nx=i+dir[0]; int ny=j+dir[1]; if(nx<0||nx>=n||ny<0||ny>=n||grid[nx][ny]==0) continue; if(!set.count(grid[nx][ny])){ cur+=mp[grid[nx][ny]]; set.insert(grid[nx][ny]); } } res=max(res,cur); } } } return res==0?n*n:res;//全1的情况下res不会进行更新。 只要有0, res至少为1 } };
方法二：并查集+枚举
查并集，可以查看每个集合中元素的数量
第一次遍历，将相邻的陆地加入到一个集合中
第二次遍历，如何相邻岛屿，那么就将它们岛屿的面积（集合的大小）加起来，注意去重。
class UnionFind{ public: vector<int> parent; vector<int> size; UnionFind(int n){ parent.resize(n*n); size.resize(n*n,1); iota(parent.begin(),parent.end(),0); } int find(int index){ if(index==parent[index]) return index; return parent[index]=find(parent[index]); } void unite(int index1,int index2){ int p1=find(index1),p2=find(index2); parent[p1]=p2; if(p1!=p2){//如果相等,会出现把size[p1]=size[p2]=0 都清空 size[p2]+=size[p1]; size[p1]=0; } } int getSize(int index){ return size[find(index)]; } }; class Solution { public: vector<vector<int>> dirs={{-1,0},{0,-1},{1,0},{0,1}}; int largestIsland(vector<vector<int>>& grid) { int n=grid.size(); UnionFind uf(n); int res=0; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(grid[i][j]==1){ for(int k=0;k<2;k++){ vector<int>& dir=dirs[k]; int nx=i+dir[0]; int ny=j+dir[1]; if(nx<0||nx>=n||ny<0||ny>=n||grid[nx][ny]==0) continue; uf.unite(nx*n+ny,i*n+j); } res=max(res,uf.getSize(i*n+j)); } } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(grid[i][j]==0){ int cur=1; unordered_set<int> set; for(vector<int>& dir:dirs){ int nx=i+dir[0]; int ny=j+dir[1]; if(nx<0||nx>=n||ny<0||ny>=n||grid[nx][ny]==0) continue; int p=uf.find(nx*n+ny); if(!set.count(p)){ cur+=uf.getSize(p); set.insert(p); } } res=max(cur,res); } } } return res; } };
