playonwords.txt

这是一个关于字符串的问题,虽然小但是很精致.

#include<stdio.h>
#include<string.h>
#define MaxN 30
#define MaxL 10001

int n=26;
int map[MaxN][MaxN],ss[MaxN];
int d1[MaxN],d2[MaxN];

void init()
{ int k,i,s,t,j;
  char ch[MaxL];
 memset(map,0,sizeof(map));
 memset(d1,0,sizeof(d1)); memset(d2,0,sizeof(d2));
 for (i=0; i<n; i++) ss[i]=i;
 scanf("%d",&k);
 for (i=0; i<k; i++)
  {scanf("%s",ch); s=ch[0]-'a'; t=ch[strlen(ch)-1]-'a';
   d1[s]++; d2[t]++;
   map[s][t]++;
   for (j=0; j<n; j++) if (ss[j]==ss[t]) ss[j]=ss[s];
  }
}

int search()
{ int i,j,k,t1=0,t2=0,x=-1;
 for (i=0; i<n; i++)
  {if (d1[i]>d2[i]+1) return 0;
   if (d2[i]>d1[i]+1) return 0;
   if (d1[i]==d2[i]+1) t1++;
   if (d2[i]==d1[i]+1) t2++;
   if (d1[i]==d2[i]&&d1[i]>0&&d2[i]>0)
    if (x!=ss[i])
     {if (x==-1) x=ss[i]; else return 0;}
  }
 if (t1==0&&t2==0) return 1;
 if (t1==1&&t2==1) return 1;
 return 0;
}

int main()
{ int testdata,i,f;
 scanf("%d",&testdata);
 for (i=0; i<testdata; i++)
  {init();
   f=search();
   if (f) printf("Ordering is possible.\n"); 
   else printf("The door cannot be opened.\n");
  }
 return 0;
}