HDU 1198

#include<stdio.h>
#include<string.h>
#define N 550
int map[N][N];
int f[N][N][5],h[N][5];
int pre[N];
int find(int n) {
if(n!=pre[n])
pre[n]=find(pre[n]);
return pre[n];
}
int main() {
int n,m,i,j,ans,f1,f2;
char ch;
    memset(f,0,sizeof(f));
memset(h,0,sizeof(h));
h[0][1]=1;h[0][4]=1;
h[1][1]=1;h[1][2]=1;
h[2][3]=1;h[2][4]=1;
h[3][2]=1;h[3][3]=1;
h[4][1]=1;h[4][3]=1;
h[5][2]=1;h[5][4]=1;
h[6][1]=1;h[6][2]=1;h[6][4]=1;
h[7][1]=1;h[7][3]=1;h[7][4]=1;
h[8][2]=1;h[8][3]=1;h[8][4]=1;
h[9][1]=1;h[9][2]=1;h[9][3]=1;
h[10][1]=1;h[10][2]=1;h[10][3]=1;h[10][4]=1;
for(i=0;i<11;i++) 
for(j=0;j<11;j++) {
if(h[i][2]&&h[j][4])
f[i][j][0]=1;
if(h[i][3]&&h[j][1])
f[i][j][1]=1;
}
while(scanf("%d%d",&n,&m),n>=0||m>=0) {
for(i=1;i<=n*m;i++)
pre[i]=i;
memset(map,0,sizeof(map));
for(i=1;i<=n;i++) {
getchar();
for(j=1;j<=m;j++) {
scanf("%c",&ch);
map[i][j]=ch-'A';
}
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++) {
if(f[map[i][j]][map[i][j+1]][0]&&j+1<=m) {
f1=find((i-1)*m+j);
f2=find((i-1)*m+j+1);
if(f1!=f2)
pre[f2]=f1;
}
if(f[map[i][j]][map[i+1][j]][1]&&i+1<=n) {
f1=find((i-1)*m+j);
f2=find(i*m+j);
if(f1!=f2)
pre[f2]=f1;
}
}
ans=0;
for(i=1;i<=n*m;i++)
if(pre[i]==i)
ans++;
printf("%d ",ans);
}
return 0;
}






   
原文地址:https://www.cnblogs.com/thefirstfeeling/p/4410933.html