学步园

              题意:

                       已知明文和密文的转换是通过二元对应关系来的...如f(A,Z)代表在明文中的A将在密文中以Z代替...并且也代表了明文中的Z在密文中以A代替...

                       现在给了一些明文的单词(至多20个)...再给了一串密文(总长度至多80)..已知这串密文是由上面某些明文的单词变换而组成的..现在问能否唯一确定密文对应的明文...

              题解:

                       直接DFS就行了....值得注意的是对于密文单词和明文单词..都先确定了长串..再依次往长度小的串确定..效率不是快一点半点..

Program:

#include <iostream>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <stdio.h>
using namespace std;
string s[2000],a[310],out[2000];
char ss[2000];
int turn[360],ans,T[360];
void dfs(int p,int n,int m)
{
      int i,x,len=s[p].length(),temp[260];
      if (p>m)
      {
              ans++;
              for (x=0;x<26;x++) T[x]=turn[x];
              return;
      }
      for (i=1;i<=n;i++)
      {
              if (len!=a[i].length()) continue;
              for (x=0;x<26;x++) temp[x]=turn[x];
              for (x=0;x<len;x++)
              {
                     if (turn[s[p][x]-'A']!=-1 && turn[s[p][x]-'A']!=a[i][x]-'A') break;
                     if (turn[a[i][x]-'A']!=-1 && turn[a[i][x]-'A']!=s[p][x]-'A') break;
                     turn[s[p][x]-'A']=a[i][x]-'A',
                     turn[a[i][x]-'A']=s[p][x]-'A';
              }
              if (x==len) dfs(p+1,n,m);
              if (ans>1) return;
              for (x=0;x<26;x++) turn[x]=temp[x];
      }
}
bool cmp(string a,string b)
{
      if (a.length()!=b.length()) return a.length()>b.length();
      return a<b;
}
int main()
{
      int n,m,len,x,i; 
      while (~scanf("%d",&n) && n)
      {
               for (i=1;i<=n;i++) scanf("%s",ss),a[i]=ss;
               sort(a+1,a+1+n,cmp);
               m=0;
               while (scanf("%s",ss) && ss[strlen(ss)-1]!='.')
                                                    s[++m]=ss,out[m]=ss;
               ss[strlen(ss)-1]='\0',s[++m]=ss,out[m]=ss;
               sort(s+1,s+1+m,cmp);
               memset(turn,-1,sizeof(turn));
               ans=0;
               dfs(1,n,m);
               if (ans==1)
               {
                     for (i=1;i<=m;i++)
                     {
                           len=out[i].length();
                           for (x=0;x<len;x++)
                                printf("%c",T[out[i][x]-'A']+'A');
                           if (i!=m) printf(" ");
                     }
                     puts(".");
               }else
                     puts("-.");
      }
      return 0;
}