2010年山东省第一届ACM大学生程序设计竞赛 Balloons (BFS)

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #include <queue>
  5 #include <string.h>
  6 #include <cmath>
  7 
  8 using namespace std;
  9 
 10 struct node
 11 {
 12     int r,c ;
 13 } p1,p2,p3;
 14 int n,cnt1,cnt2 ;
 15 char a[110][110] ;
 16 int flag[110][110];
 17 int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}} ;
 18 int dir1[8][2] = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}} ;
 19 
 20 void BFS1(int i,int j)
 21 {
 22     queue<node>Q ;
 23     p1.r = i ;
 24     p1.c = j ;
 25     Q.push(p1) ;
 26     flag[i][j] = 1 ;
 27     while(!Q.empty())
 28     {
 29         p2 = Q.front() ;
 30         Q.pop() ;
 31         for(int i = 0 ; i < 4 ; i++)
 32         {
 33             int xx = p2.r+dir[i][0] ;
 34             int yy = p2.c+dir[i][1] ;
 35             if(xx >= 0 && yy >= 0 && xx < n && yy < n && !flag[xx][yy] && a[xx][yy] == ‘1‘)
 36             {
 37                 flag[xx][yy] = 1 ;
 38                 p1.r = xx ;
 39                 p1.c = yy ;
 40                 Q.push(p1) ;
 41             }
 42         }
 43     }
 44 }
 45 void BFS2(int i,int j)
 46 {
 47     queue<node>Q ;
 48     p1.r = i ;
 49     p1.c = j ;
 50     Q.push(p1) ;
 51     flag[i][j] = 1 ;
 52     while(!Q.empty())
 53     {
 54         p2 = Q.front() ;
 55         Q.pop() ;
 56         for(int i = 0 ; i < 8 ; i++)
 57         {
 58             int xx = p2.r+dir1[i][0] ;
 59             int yy = p2.c+dir1[i][1] ;
 60             if(xx >= 0 && yy >= 0 && xx < n && yy < n && !flag[xx][yy] && a[xx][yy] == ‘1‘)
 61             {
 62                 flag[xx][yy] = 1 ;
 63                 p1.r = xx ;
 64                 p1.c = yy ;
 65                 Q.push(p1) ;
 66             }
 67         }
 68     }
 69 }
 70 int main()
 71 {
 72     int cas = 1 ;
 73     while(~scanf("%d",&n) && n)
 74     {
 75         for(int i = 0 ; i < n ; i++)
 76                 scanf("%s",a[i]) ;
 77         cnt1 = cnt2 = 0;
 78         memset(flag,0,sizeof(flag)) ;
 79         for(int i = 0 ; i < n ; i++)
 80             for(int j = 0 ; j < n ; j++)
 81             {
 82                 if(a[i][j] == ‘1‘ && !flag[i][j])
 83                 {
 84                     BFS1(i,j) ;
 85                     cnt1++ ;
 86                 }
 87             }
 88         memset(flag,0,sizeof(flag)) ;
 89         for(int i = 0 ; i < n ; i++)
 90             for(int j = 0 ; j < n ; j++)
 91             {
 92                 if(a[i][j] == ‘1‘ && !flag[i][j])
 93                 {
 94                     BFS2(i,j) ;
 95                     cnt2++ ;
 96                 }
 97             }
 98         printf("Case %d: %d %d\n\n",cas++,cnt1,cnt2) ;
 99     }
100     return 0;
101 }