小岛面积-期末考试试题

小岛面积-期末考试试题

时间： 1ms        内存：128M

描述：

上面矩阵的中的1代表海岸线，0代表小岛。求小岛面积（即被1中包围的0的个数）的最大值。

输入：

第一行输入一个整数N(1<=N<=100)，表示输入方阵的维数

输入一个N维方阵

输出：

小岛面积

示例输入：

6
1 1 1 1 1 1
1 1 0 0 0 1
1 0 0 0 1 0
1 1 0 1 1 1
0 1 0 1 0 0
1 1 1 1 1 1

示例输出：

8

提示：

参考答案（内存最优[1120]）：

#include<stdio.h>
int N;
int count=0;
int main()
{
    void dsr(int x,int y,int c[N][N]);
    scanf("%d",&N);
    int a[N][N];
    int d[N][N];
    int i,j;
    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
        scanf("%d",&a[i][j]);
    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
    {
        dsr(i,j,a);
        d[i][j]=count;
        count=0;
    }
    int max=0;
    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
    {
            if(max<d[i][j])
                max=d[i][j];
    }
    printf("%d",max);
}
void dsr(int x,int y,int c[N][N])
{
    if(x>N || y>N || x<0 || y<0 || c[x][y]!=0)
        return ;
    if(c[x][y]==0)
    {
        count++;
        c[x][y]++;
        dsr(x+1,y,c);
        dsr(x-1,y,c);
        dsr(x,y+1,c);
        dsr(x,y-1,c);
    }
    return ;
}

参考答案（时间最优[1]）：

#include<stdio.h>
int main()
{
    int cnt=0;
    int N;
    scanf("%d",&N);
    int a[N][N];
    int i,j;
    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
        scanf("%d",&a[i][j]);
    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
        {
            if(a[i][j]==0&&(a[i-1][j]==0||a[i][j-1]==0||a[i][j+1]==0||a[i+1][j]==0))
            cnt++;
            if(a[i][j]==0&&a[i][j+1]==0&&(a[i-1][j]==1&&a[i][j-1]==1&&a[i+1][j]==1&&a[i-1][j+1]==1&&a[i][j+2]==1&&a[i+1][j+1]==1))
                cnt-=2;
        }
    printf("%d",cnt);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。