ITKeyword,专注技术干货聚合推荐

注册 | 登录

PPOJ 2386 Lake Counting(DFS)

h549570564 分享于 2013-10-28

推荐:poj2386 Lake Counting(简单DFS)

转载请注明出处:http://blog.csdn.net/u012860063viewmode=contents 题目链接:http://poj.org/problemid=1562 Description Due to recent rains, water has

2020腾讯云“6.18”活动开始了!!!(巨大优惠重现!4核8G,5M带宽 1999元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1059

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

题意:有一块N*M的土地,有些地方有水,有些地方很干燥,有水标记为'W',干燥为'.'。八连通的积水被认为是连接在一起的(即两个都在同一个九宫格内),问一共有多少摊积水。

方法:对每块有水的地方进行一次DFS,范围为其周围8个位置,DFS后将其标记为干燥地,统计一共需要DFS即可。

推荐:POJ2386 Lake Counting 【DFS】

Lake Counting Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 20782   Accepted: 10473 Description Due to recent rains, water has pooled i

注意:W是大写。

#include<stdio.h>
#include<string.h>
int dx[10]={-1,-1,-1,0,0,1,1,1};
int dy[10]={-1,0,1,-1,1,-1,0,1};
char field[100+10][100+10];
int n,m;

void dfs(int x,int y)
{
    field[x][y]='.';
    int i,j;
    for(i=0;i<=7;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a<=n&&a>=1&&b<=m&&b>=1&&field[a][b]=='W')
            dfs(a,b);
    }
    return ;
}

int main()
{
    int i,j,ans=0;
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d%d",&n,&m);
    getchar();
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            scanf("%c",&field[i][j]);
        getchar();
    }
    /*for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            printf("%c",field[i][j]);
        printf("\n");
    }*/
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(field[i][j]=='W')
                dfs(i,j),ans++;
    printf("%d\n",ans);
    return 0;
}


 

推荐:POJ 2386 Lake Counting(dfs or bfs)

Lake Counting Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 24999 Accepted: 12619 Description Due to recent rains, water has pooled in va

题意:有一块N*M的土地,有些地方有水,有些地方很干燥,有水标记为'W',干燥为'.'。八连通的积水被认为是连接在一起的(即两个都在同一个九宫格内),问一共有多少摊积水。 方法:对每块有水的地

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。