题目
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
示例 1：
输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]] 输出：6 解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
示例 2：
输入：grid = [[0,0,0,0,0,0,0,0]] 输出：0
解题
方法一：dfs
class Solution { public: int m,n; int count=0; int res=0; vector<vector<int>> dirs={{-1,0},{0,-1},{1,0},{0,1}}; void dfs(vector<vector<int>>& grid,int x,int y){ if(x<0||x>=m||y<0||y>=n||grid[x][y]==0) return; grid[x][y]=0; count++; res=max(res,count); for(vector<int>& dir:dirs){ int nx=x+dir[0]; int ny=y+dir[1]; dfs(grid,nx,ny); } } int maxAreaOfIsland(vector<vector<int>>& grid) { m=grid.size(),n=grid[0].size(); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]!=1) continue; count=0; dfs(grid,i,j); } } return res; } };
方法二：并查集
class UnionFind{ public: vector<int> parent; vector<int> size; UnionFind(int m){ parent.resize(m); iota(parent.begin(),parent.end(),0); size=vector<int>(m,1); } int find(int index){ if(parent[index]==index) return index; return parent[index]=find(parent[index]); } void unite(int index1,int index2){ int p1=find(index1); int p2=find(index2); parent[p1]=p2; if(p1!=p2){ size[p2]+=size[p1]; size[p1]=0; } } int getSize(int index){ return size[find(index)]; } }; class Solution { public: int m,n; vector<vector<int>> dirs={{-1,0},{0,-1}}; int node(int i,int j){ return i*n+j; } int maxAreaOfIsland(vector<vector<int>>& grid) { m=grid.size(),n=grid[0].size(); UnionFind uf(m*n); int res=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]==1){ for(vector<int>& dir:dirs){ int nx=i+dir[0]; int ny=j+dir[1]; if(nx<0||nx>=m||ny<0||ny>=n||grid[nx][ny]==0) continue; uf.unite(node(i,j),node(nx,ny)); } res=max(res,uf.getSize(node(i,j))); } } } return res; } };
