山东省第一届ACM大学生程序设计竞赛(原题)—I—Balloons

The last case is followed by a line containing one zero.

For each case, print the case number (1, 2 …) and the connected block’s numbers with Saya and Kudo’s definition. Your output format should imitate the sample output. Print a blank line after each test case.

0

Case 1: 3 2

简单DFS，这道题刚开始还没咋看懂，后来才醒悟就是两个DFS，

这个和杭电油田那题目类似，前面的搜索找的四个方向的，后面的找的是八个方向的。。。

详情可见：

http://blog.csdn.net/lttree/article/details/19908339（八个方向的）

#include <iostream>  
  
using namespace std;  
char map1[101][101];  
char map2[101][101];  
int n,dis[4][2]={0,1,0,-1,1,0,-1,0};  
int dis2[8][2]={-1,-1,-1,0,-1,1,0,-1,0,1,1,1,1,0,1,-1};  
bool judge(int x,int y,int flag)  
{  
    if(x<0 || y<0 || x>=n || y>=n)  return 0;  
    if(flag==1)  
    {  
        if(map1[x][y]==‘0‘)   return 0;  
    }  
    else  
    {  
        if(map2[x][y]==‘0‘)   return 0;  
    }  
    return 1;  
}  
  
void dfs1(int x,int y)  
{  
    map1[x][y]=‘0‘;  
    int i,xx,yy;  
    for(i=0;i<4;++i)  
    {  
        xx=x+dis[i][0];  
        yy=y+dis[i][1];  
        if(judge(xx,yy,1))  
        {  
            dfs1(xx,yy);  
        }  
    }  
    return;  
}  
  
void dfs2(int x,int y)  
{  
    map2[x][y]=‘0‘;  
    int i,xx,yy;  
    for(i=0;i<8;++i)  
    {  
        xx=x+dis2[i][0];  
        yy=y+dis2[i][1];  
        if(judge(xx,yy,2))  
        {  
            dfs2(xx,yy);  
        }  
    }  
    return;  
}  
  
int main()  
{  
    int test,sum1,sum2;  
    int i,j;  
    test=1;  
    while(cin>>n && n)  
    {  
        for(i=0;i<n;++i)  
            for(j=0;j<n;++j)  
            {  
                cin>>map1[i][j];  
                map2[i][j]=map1[i][j];  
            }  
  
        sum1=0;  
        for(i=0;i<n;++i)  
        {  
            for(j=0;j<n;++j)  
            {  
                if(map1[i][j]==‘1‘)  
                {  
                    dfs1(i,j);  
                    ++sum1;  
                }  
            }  
        }  
        sum2=0;  
        for(i=0;i<n;++i)  
        {  
            for(j=0;j<n;++j)  
            {  
                if(map2[i][j]==‘1‘)  
                {  
                    dfs2(i,j);  
                    ++sum2;  
                }  
            }  
        }  
  
        cout<<"Case "<<test++<<": "<<sum1<<" "<<sum2<<endl;  
        cout<<endl;  
    }  
    return 0;  
}  

山东省第一届ACM大学生程序设计竞赛(原题)—I—Balloons,布布扣,bubuko.com

山东省第一届ACM大学生程序设计竞赛(原题)—I—Balloons

原文：http://blog.csdn.net/lttree/article/details/23603413