2152 sdut Balloons （dfs）

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 char map[110][110],cpy[110][110];
 5 int vis[110][110];
 6 
 7 int dx[4]={0,0,1,-1};
 8 int dy[4]={1,-1,0,0};
 9 
10 int tdx[8]={0,0,1,-1,1,-1,1,-1};
11 int tdy[8]={1,-1,0,0,1,1,-1,-1};
12  int n,i,j,cnt1,cnt2;
13 
14 void dfs(int i,int j)
15 {
16     int k;
17     for(k=0; k<4; k++)
18     {
19         int nx=i+dx[k],ny=j+dy[k];
20         if(nx>=0&&nx<n&&ny>=0&&ny<n&&!vis[nx][ny]&&map[nx][ny]=='1')
21         {
22             vis[nx][ny]=1;
23             dfs(nx,ny);
24         }
25     }
26 };
27 
28 void dfs2(int i,int j)
29 {
30    int k;
31    for(k=0; k<8; k++)
32    {
33        int nx=i+tdx[k],ny=j+tdy[k];
34        if(nx>=0&&nx<n&&ny>=0&&ny<n&&!vis[nx][ny]&&map[nx][ny]=='1')
35         {
36             vis[nx][ny]=1;
37             dfs2(nx,ny);
38         }
39    }
40 };
41 int main()
42 {
43     int t=1;
44     while(~scanf("%d",&n)&&n)
45     {
46         cnt1=0; cnt2=0;
47         for(i=0; i<n; i++)
48         {
49             scanf("%s",map[i]);
50             strcpy(cpy[i],map[i]);
51         }
52 
53         memset(vis,0,sizeof(vis));
54         for(i=0; i<n; i++)
55         for(j=0; j<n; j++)
56         {
57             if(map[i][j]=='1'&&!vis[i][j])
58             {
59                 dfs(i,j);
60                 cnt1++;
61                 vis[i][j]=1;
62             }
63         }
64 
65         memset(vis,0,sizeof(vis));
66         for(i=0; i<n; i++)
67         {
68             strcpy(map[i],cpy[i]);
69         }
70 
71         for(i=0; i<n; i++)
72         for(j=0; j<n; j++)
73         {
74             if(map[i][j]=='1'&&!vis[i][j])
75             {
76                 cnt2++;
77                 vis[i][j]=1;
78                 dfs2(i,j);
79             }
80         }
81         printf("Case %d: %d %d\n\n",t,cnt1,cnt2);
82         t++;
83     }
84 }
85
View Code
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2152