leetcode-695. Max Area of Island(C语言)

问题描述

给定一个二维数组，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));
}


;

Popular Programs