poj 3620

题意:给出一个矩阵,其中有些格子干燥、有些潮湿。

      如果一个潮湿的格子的相邻的四个方向有格子也是潮湿的,那么它们就可以构成更大

      的湖泊,求最大的湖泊。

      也就是求出最大的连在一块儿的潮湿的格子的数目。

#include<iostream>
#include<cstring>
using namespace std;
int aa[105][105]={0};
int dir[4][2]={-1,0,1,0,0,-1,0,1};
int sum=0,ans=0,n,m,k;
void dfs(int a,int b)
{
    int a1,b1;
    ans++;
    aa[a][b]=0;                 
    for(int i=0;i<4;i++)
    {
        a1=a+dir[i][0];
        b1=b+dir[i][1];
        if(a1>=1&&a1<=n&&b1>=1&&b1<=m&&aa[a1][b1])
            dfs(a1,b1);
            //不用回溯的原因,因为只要是能连续到达的店连成湖的肯定都能连一块的;
            
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<k;i++)
    {int x,y;
        cin>>x>>y;

        aa[x][y]=1;

    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
    {   if(aa[i][j])
    {   ans=0;
        dfs(i,j);
        if(ans>sum)sum=ans;
    }
    }
    cout<<sum<<endl;


    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ 2531

    瑾诺学长
  • poj 1562 dfs

    瑾诺学长
  • poj 2681 字符串

    瑾诺学长
  • 洛谷P2770 航空路线问题(费用流)

    为了满足流量的限制,肯定会想到拆点,把每个点拆为两个,连流量为$1$,费用为$1$的边

    attack
  • P1113 杂务 拓扑

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    用户2965768
  • 图论建图

    图论建图无外乎邻接表建图和链式前向星建图,不要问我是怎么知道的,要是你的学校逼你打图论位的话你就知道了。

    ACM算法日常
  • UESTC 1599 wtmsb【优先队列+排序】

    题目链接:UESTC 1599 wtmsb 题意:给你一组数,每一次取出两个最小的数,将这两个数的和放入这组数中,直到这组数只剩下一个,求最后剩下那个数的大小!...

    Angel_Kitty
  • hdu1030

    @坤的
  • 洛谷P1966 火柴排队(逆序对)

    首先要保证权值最小,不难想到一种贪心策略,即把两个序列中rank相同的数放到同一个位置

    attack
  • POJ 刷题系列:2993. Emag eht htiw Em Pleh

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447

扫码关注云+社区

领取腾讯云代金券