NYOJ 1237 最大岛屿（深搜）

描述

神秘的海洋，惊险的探险之路，打捞海底宝藏，激烈的海战，海盗劫富等等。加勒比海盗，你知道吧？杰克船长驾驶着自己的的战船黑珍珠1号要征服各个海岛的海盜，最后成为海盗王。这是一个由海洋、岛屿和海盗组成的危险世界。面对危险重重的海洋与诡谲的对手，如何凭借智慧与运气，建立起一个强大的海盗帝国。

杰克船长手头有一张整个海域的海图，上面密密麻麻分布着各个海屿的位置及面积。他想尽快知道整个海域共有多少岛屿以及最大岛屿的面积。

输入

第1行:M N T，表示海域的长，宽及一个单位表示的面积大小接下来有M行 ,每行有N个01组成的序列以及其中穿插一些空格。0表示海水，1表示陆地，其中的空格没用，可以忽略掉。
输出

输出一行，有2个整数，一个空格间隔，表示整个海域的岛屿数，以及最大岛屿的面积
样例输入

8 16 99

00000000 00000000

0000110011000000

0001111000111000

0000000 00 0000000

00111 111000001 10

001110000 0000000

0100001111 111100

0000000000000000
样例输出

5 990
提示

①若一个陆地八个方向之一（上、下、左、右、左上、右上、左下、右下）的位置也是陆地，则视为同一个岛屿。② 假设第一行，最后一行，第一列，最后一列全为0.③ 1<M, N≤500 1<T≤100000

分析：

这道题呢首先的一个难点就是输入的时候中间有空格，还的吧空格去掉，这样的话可以每次只输入一个字符，如果字符是'0'或'1'的话，才放入到合适的位置，否则就不进行处理。

然后我们要找岛屿的个数以及面积最大的岛屿，

代码：

#include<stdio.h>

#include<algorithm>

#include<string.h>

char a[1005][1005];

int  n,m,maxMian=-1,mian=1;

int next[8][2]= {0,1,1,1,1,-1,-1,-1,-1,1,1,0,0,-1,-1,0};

void dfs(int x,int y)

{

    int k,tx,ty;

    for(k=0; k<=7; k++)

    {

        tx=x+next[k][0];

        ty=y+next[k][1];

        if(tx<1||tx>n||ty<1||ty>m)

            continue;

        if(a[tx][ty]=='1')

        {

            mian++;

            if(mian>maxMian)///找出秒你最大的岛屿

                maxMian=mian;

            a[tx][ty]='0';

            dfs(tx,ty);

        }

    }

    return;

}

int main()

{

    int s;

    while(~scanf("%d%d%d",&n,&m,&s))

    {

        maxMian=-1,mian=1;

        char ch;

        if(n==0)

            break;

        int sum=0;

        memset(a,'0',sizeof(a));

        int i,j;

        for(i=1; i<=n; i++)///输入的时候去掉空格，认为是一种比较巧妙地方法

        {

            for(j=1; j<=m;)

            {

                scanf(" %c",&ch);

                if(ch=='0'||ch=='1')

                {

                    a[i][j]=ch;

                    j++;

                }

            }

        }

        for(i=1; i<=n; i++)

            for(j=1; j<=m; j++)

            {

                if(a[i][j]=='1')///相当于可以以任何一个满足小岛屿开始找它的周围的岛屿

                {

                    mian=1;///当前小岛的个数

                    sum++;///总共的岛屿个数

                    a[i][j]='0';

                    dfs(i,j);

                }

            }

        printf("%d %d\n",sum,maxMian*s);

    }

    return 0;

}

巴特西

NYOJ 1237 最大岛屿（深搜）

最新文章

热门文章

巴特西

NYOJ 1237 最大岛屿 （深搜）

最新文章

热门文章

NYOJ 1237 最大岛屿（深搜）