问题描述
给定一个二维数组，1代表岛屿，0代表海洋。岛屿在垂直或者水平方向上相连。求面积最大的岛屿。
[[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.
代码
#include <stdio.h>
#include <stdlib.h>
int find(int **grid,int gridRowSize,int gridColSize,int i,int j){
if(i<0||i>=gridRowSize||j<0||j>gridColSize)return 0;
if(grid[i][j]==1){
grid[i][j]=0;
return 1+find(grid,gridRowSize,gridColSize,i-1,j)+find(grid,gridRowSize,gridColSize,i+1,j)
+find(grid,gridRowSize,gridColSize,i,j-1)+find(grid,gridRowSize,gridColSize,i,j+1);
}
else return 0;
}
int maxAreaOfIsland(int** grid, int gridRowSize, int gridColSize) {
int max=0;
for(int i=0;i<gridRowSize;i++){
for(int j=0;j<gridColSize;j++){
if(grid[i][j]!=0){
int k= find(grid,gridRowSize,gridColSize,i,j);
if(k>max){
max=k;
}
}
}
}
return max;
}
int main()
{
int m=8,n=13;
int a[8][13]={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};
int **grid=(int **)malloc(sizeof(int *)*m);
for(int i=0;i<m;i++){
grid[i]=(int *)malloc(sizeof(int)*n);
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
grid[i][j]=a[i][j];
}
}
printf("%d",maxAreaOfIsland(grid,8,13));
}