怎么求岛屿最大面积问题

Question

#include <stdio.h>
#define NUM 10

int ocean[NUM][NUM] = {        //面积为最大为15
 1,1,0,0,0,0,0,0,1,0
,1,1,1,1,0,0,0,0,0,0
,0,1,0,0,0,1,0,0,1,1
,0,0,1,1,1,1,1,0,0,1
,0,0,1,1,1,0,0,0,0,0
,1,0,1,0,1,0,0,0,0,0
,1,0,1,1,1,0,0,0,0,0
,0,0,1,0,0,0,0,0,1,0
,0,0,0,0,0,0,0,0,1,1
,0,0,0,0,0,0,0,0,0,0 };

int temp[NUM][NUM];            //标记走过的位置 

int Next[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };        //四种走法，右下左上 

int Max = -1;            //最大岛屿面积 

int area;

void dfs(int x, int y) {

    int tx,ty;
    
    if(area>Max){
        Max=area;
    }
    
    for(int k=0;k<=3;k++){
        tx=x+Next[k][0];
        ty=y+Next[k][1];
        
        if(tx>NUM-1||tx<0||ty<0||ty>NUM-1){
            continue;
        }
        
        if(ocean[tx][ty]==1&&temp[tx][ty]==0){    
            temp[tx][ty]=1;
            area++;        //自增 1 表示ocean[x][y]的面积 ，并不是oceam[tx][ty] 
            dfs(tx,ty);
        }
        
    }
}

int main() {
    
    for(int i=0;i<=NUM-1;i++){
        for(int j=0;j<=NUM-1;j++){
            if(ocean[i][j])
            dfs(i, j);
        }
        area=0;
    }
    
    for(int i=0;i<=NUM-1;i++){
        for(int j=0;j<=NUM-1;j++){
            printf("%d ",temp[i][j]);
        }
        printf("\n");
    } 

//    dfs(3,3);

    printf("最大岛屿面积为%d\n", Max);

    return 0;
}

我从（3,3）开始测试岛屿最大面积的时候，结果是正确答案15，但是我用两层for循环测试每个地方的最大岛屿面积，结果却是18

Answer 1

你可以先拿到岛屿的数量，再想办法求哪个岛屿最大