题意:判断图中的图形有几个集合。
这道题做的郁闷死我了,为了找开始字母的错误一个一个匹对。
这道题让我也懂得了表格的位置可以代表并查集的点,这样每个都不一样,而我想的那种用字母是否本身来判断有多少个集合是错误的,很明显一个字母不会只出现一次。而且在计算位置的时候也出错了,应该i*列代表的第几行
#include<stdio.h>
#include<string.h>
const int MAXN=110;
int total;
int gra_row[MAXN][MAXN],gra_col[MAXN][MAXN];
int rank[2510],father[2510];
void init()
{
memset(gra_row,0,sizeof(gra_row));
memset(gra_col,0,sizeof(gra_col));
gra_row['B']['A']=gra_row['B']['C']=gra_row['B']['F']=gra_row['B']['G']=gra_row['B']['H']=gra_row['B']['I']=gra_row['B']['K']=1;
gra_row['D']['A']=gra_row['D']['C']=gra_row['D']['F']=gra_row['D']['G']=gra_row['D']['H']=gra_row['D']['I']=gra_row['D']['K']=1;
gra_row['F']['A']=gra_row['F']['C']=gra_row['F']['F']=gra_row['F']['G']=gra_row['F']['H']=gra_row['F']['I']=gra_row['F']['K']=1;
gra_row['G']['A']=gra_row['G']['C']=gra_row['G']['F']=gra_row['G']['G']=gra_row['G']['H']=gra_row['G']['I']=gra_row['G']['K']=1;
gra_row['I']['A']=gra_row['I']['C']=gra_row['I']['F']=gra_row['I']['G']=gra_row['I']['H']=gra_row['I']['I']=gra_row['I']['K']=1;
gra_row['J']['A']=gra_row['J']['C']=gra_row['J']['F']=gra_row['J']['G']=gra_row['J']['H']=gra_row['J']['I']=gra_row['J']['K']=1;
gra_row['K']['A']=gra_row['K']['C']=gra_row['K']['F']=gra_row['K']['G']=gra_row['K']['H']=gra_row['K']['I']=gra_row['K']['K']=1;
gra_col['C']['A']=gra_col['C']['B']=gra_col['C']['E']=gra_col['C']['G']=gra_col['C']['H']=gra_col['C']['J']=gra_col['C']['K']=1;
gra_col['D']['A']=gra_col['D']['B']=gra_col['D']['E']=gra_col['D']['G']=gra_col['D']['H']=gra_col['D']['J']=gra_col['D']['K']=1;
gra_col['E']['A']=gra_col['E']['B']=gra_col['E']['E']=gra_col['E']['G']=gra_col['E']['H']=gra_col['E']['J']=gra_col['E']['K']=1;
gra_col['H']['A']=gra_col['H']['B']=gra_col['H']['E']=gra_col['H']['G']=gra_col['H']['H']=gra_col['H']['J']=gra_col['H']['K']=1;
gra_col['I']['A']=gra_col['I']['B']=gra_col['I']['E']=gra_col['I']['G']=gra_col['I']['H']=gra_col['I']['J']=gra_col['I']['K']=1;
gra_col['J']['A']=gra_col['J']['B']=gra_col['J']['E']=gra_col['J']['G']=gra_col['J']['H']=gra_col['J']['J']=gra_col['J']['K']=1;
gra_col['K']['A']=gra_col['K']['B']=gra_col['K']['E']=gra_col['K']['G']=gra_col['K']['H']=gra_col['K']['J']=gra_col['K']['K']=1;
}
void Make_set()
{
for(int i=0;i<=2505;i++)
{
father[i]=i;
rank[i]=0;
}
}
int Find(int x)
{
if(x!=father[x])
{
return father[x]=Find(father[x]);
}
return x;
}
void Union(int x,int y)
{
x=Find(x);
y=Find(y);
if(x==y) return ;
total--;
if(rank[x]>rank[y]) father[y]=x;
else
{
if(rank[x]==rank[y])
{
rank[y]++;
}
father[x]=y;
}
}
int main()
{
int n,m,i,j;
int a,b;
char str[MAXN][MAXN];
init();
while(scanf("%d%d",&n,&m))
{
Make_set();
memset(str,0,sizeof(str));
total=m*n;
if(m<0 || n<0) break;
for(i=0;i<n;i++)
{
scanf("%s",str[i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(gra_row[str[i][j]][str[i][j+1]]==1) //Union(str[i][j],str[i][j+1]);
{
a=i*m+j;
b=a+1;
Union(a,b);
}
if(gra_col[str[i][j]][str[i+1][j]]==1) //Union(str[i][j],str[i+1][j]);
{
a=i*m+j;
b=(i+1)*m+j;
Union(a,b);
}
}
}
printf("%d\n",total);
}
return 0;
}
简便一点的写法
char up[8]={"ABEGHJK"},
down[8]={"CDEHIJK"},
left[8]={"ACFGHIK"},
right[8]={"BDFGIJK"};
int row_link[30][30]={0},column_link[30][30]={0};
void init()
{
int i,j;
for(i=0;i<7;i++)
{
for(j=0;j<7;j++)
{
column_link[down[i]-'A'][up[j]-'A']=1;
row_link[right[i]-'A'][left[j]-'A']=1;
}
}
}