首页 > 试题广场 >

岛屿的最大面积

[编程题]岛屿的最大面积
  • 热度指数：3024 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个用 n*m 矩阵表示的群岛的地图，其中 1 表示岛屿， 0 表示海洋，每个岛屿的水平或竖直方向相邻的岛屿可以视为连在一起的岛屿，每一块岛屿视为面积为 1 ，请问面积最大的岛屿是多少。

例如：
当输入[[1,0],[0,1]]时，对应的地图为：

只有在水平或竖直方向相邻的岛屿可以连在一起，所以每个岛屿互相独立。最大面积是1

当输入[[1,1],[1,0]]时，对应的地图为：

三块岛屿可以连在一起，最大面积是3

数据范围：
示例1

输入

[[1,0],[0,1]]

输出

1

说明

如题面解释
示例2

输入

[[1,1],[1,0]]

输出

3

说明

如题面解释
示例3

输入

[[0]]

输出

0
算法知识视频讲解
添加回答
C
企鹅暴打皮卡丘头像 企鹅暴打皮卡丘
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param grid int整型二维数组 
 * @param gridRowLen int grid数组行数
 * @param gridColLen int* grid数组列数
 * @return int整型
 */
 int max(int a,int b)
 {
     if(a>b)
     return a;
     return b;
 }
 int dfs(int **grid,int **visit,int i,int j,int n,int m)
 {
    visit[i][j]=1;
    int square=1;
    if(i-1>0 && visit[i-1][j]==0 &&grid[i-1][j]==1)
        square=square+dfs(grid,visit,i-1,j,n,m);
    if(i+1<n && visit[i+1][j]==0 &&grid[i+1][j]==1)
        square=square+dfs(grid,visit,i+1,j,n,m);
    if(j+1<m && visit[i][j+1]==0 &&grid[i][j+1]==1)
        square=square+dfs(grid,visit,i,j+1,n,m);
    if(j-1>0 && visit[i][j-1]==0 &&grid[i][j-1]==1)
        square=square+dfs(grid,visit,i,j-1,n,m);
     return square;
 }
int maxAreaIsland(int** grid, int gridRowLen, int* gridColLen ) {
    int n=*gridColLen;
    int m=gridRowLen;
    int maxsquare=0;
    int **visit;
    visit=(int**)malloc(sizeof(int*)*m);
    for(int i=0;i<m;i++)
        visit[i]=(int*)malloc(sizeof(int)*n);
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
            visit[i][j]=0;
    }
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(grid[i][j]==1 && visit[i][j]==0)
            {
                maxsquare=max(dfs(grid,visit,i,j,m,n),maxsquare);
            }
        }
    }
    return maxsquare;
}
发表于 2022-09-30 11:01:31 回复(0)
提交观点

问题信息

递归
难度：
1条回答 1992浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号