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 阅读(298)
评论(0) 编辑 收藏 引用