poj1164(dfs)城堡问题

2017年07月28日 10点热度 0人点赞 0条评论

poj1164(dfs)城堡问题poj1164(dfs)城堡问题

//建图的方式好像没有别人好,我把墙也算到图里面去了
#include
#include
#include
using namespace std;
int a[102][102],n,m,ans;
int dir[4][2]= {2,0,0,2,-2,0,0,-2};
int t[4][2]= {1,0,0,1,-1,0,0,-1};
void dfs(int x1,int y1)
{
    int x,y;
    for(int i=0; i<4; ++i)
    {
        x=x1+dir[i][0],y=y1+dir[i][1];
        if(!a[x][y]&&!a[x1+t[i][0]][y1+t[i][1]])
        {
            ++ans;
            a[x][y]=1;
            dfs(x,y);
        }
    }
}
int main()
{
    int t;
    while(~scanf("%d%d",&n,&m))
    {
        memset(a,0,sizeof(a));
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=m; ++j)
            {
                scanf("%d",&t);
                if(t&1) a[i*2][j*2-1]=1;
                if(t&2) a[i*2-1][j*2]=1;
                if(t&4) a[i*2][j*2+1]=1;
                if(t&8) a[i*2+1][j*2]=1;
            }
        int mx=0,cnt=0;
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=m; ++j)
                if(!a[2*i][2*j])
                {
                    cnt++;
                    a[i*2][j*2]=1;
                    ans=1;
                    dfs(2*i,2*j);
                    mx=max(mx,ans);
                }
        printf("%dn%dn",cnt,mx);
    }
    return 0;
}
未经允许不得转载!poj1164(dfs)城堡问题

update

纸上得来终觉浅, 绝知此事须躬行。