随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:    对给定的11个图进行分类,判断相邻图是否相连,并查集判断一下就行    
 4 How to Do:    并查集
 5   */
 6 #include <iostream>
 7 #include <string.h>
 8 #include <algorithm>
 9 using namespace std;
10 struct point{
11     int no;
12     int pre;
13 }unit[2500];
14 bool field[11][4];
15 int m,n,sum;
16 int findSet(int x){
17     if(unit[x].pre!=x)
18         unit[x].pre=findSet(unit[x].pre);
19     return unit[x].pre;
20 }
21 void merge(int x,int y){
22     x=findSet(x);
23     y=findSet(y);
24     if(x!=y){
25         unit[x].pre=y;
26         sum--;
27     }
28 }
29 void init(){
30     memset(field,true,sizeof(field));
31     int i;
32     for(i=0;i<m*n;i++)
33         unit[i].pre=i;
34     field[0][2]=field[0][3]=false;
35     field[1][0]=field[1][3]=false;
36     field[2][1]=field[2][2]=false;
37     field[3][0]=field[3][1]=false;
38     field[4][0]=field[4][2]=false;
39     field[5][1]=field[5][3]=false;
40     field[6][3]=false;
41     field[7][2]=false;
42     field[8][1]=false;
43     field[9][0]=false;
44 }
45 int main(){
46     //freopen("in.txt","r",stdin);
47     while (scanf("%d%d",&m,&n)!=EOF){
48         if(m==-1&&n==-1)//行 列
49             break;
50         init();
51         int i,j,k;
52         char ch;
53         for(i=0,k=0;i<m;i++)
54             for(j=0;j<n;j++){
55                 cin>>ch;
56                 unit[k].no=ch-'A';
57                 k++;
58             }
59         sum=m*n;
60         for(i=0;i<m*n;i++){
61             int no=unit[i].no;
62             if((i+1)%n!=0){
63                 if(field[no][2]&&field[unit[i+1].no][0])//右边与左翼
64                     merge(i,i+1);
65             }
66             if(i%n!=0){
67                 if(field[no][0]&&field[unit[i-1].no][2])
68                     merge(i,i-1);
69             }
70             if(i-n>=0){
71                 if(field[no][1]&&field[unit[i-n].no][3])
72                     merge(i,i-n);
73             }
74             if(i+n<m*n){
75                 if(field[no][3]&&field[unit[i+n].no][1])
76                     merge(i,i+n);
77             }
78         }
79         printf("%d\n",sum);
80     }
81     return 0;
82 }
83 
posted on 2012-03-15 20:17 Leo.W 阅读(291) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理