某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。
现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。
输入格式：
第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。
接下来W行，每行两个字母,表示W可以用这两个字母替代。
接下来I行，每行两个字母,表示I可以用这两个字母替代。
接下来N行，每行两个字母,表示N可以用这两个字母替代。
接下来G行，每行两个字母,表示G可以用这两个字母替代。
最后一行一个长度不超过Len的字符串。表示这个玩具的名字。
输出格式：
一行字符串，该名字可能由哪些字母变形而得到。（按照WING的顺序输出）
如果给的名字不能由任何一个字母变形而得到则输出“The name is wrong!”
#include<bits/stdc++.h> using namespace std; int num[4],flg[5][18][3],bol[250][250][5],ref[5]; char a[250]; char b[5],ma[9]={‘w‘,‘W‘,‘I‘,‘N‘,‘G‘}; bool dfs(int l,int r,int c) { if(bol[l][r][c]!=-1)return bol[l][r][c]; for(int t=1;t<=num[c];t++) for(int k=l;k<r;k++) if(dfs(l,k,flg[c][t][1])&&dfs(k+1,r,flg[c][t][2])) return bol[l][r][c]=1; return bol[l][r][c]=0; } int main() { memset(bol,-1,sizeof(bol)); int len,flag=0; ref[‘W‘]=1;ref[‘I‘]=2;ref[‘N‘]=3;ref[‘G‘]=4; for(int i=1;i<=4;i++)cin>>num[i]; for(int i=1;i<=4;i++) for(int j=1;j<=num[i];j++) { cin>>b[0]>>b[1]; flg[i][j][1]=ref[b[0]]; flg[i][j][2]=ref[b[1]]; } cin>>a; len=strlen(a); for(int i=1;i<=len;i++)bol[i][i][ref[a[i-1]]]=1; for(int i=1;i<=4;i++) if(dfs(1,len,i)){cout<<ma[i];flag=1;} if(!flag)cout<<"The name is wrong!"; }
原文：https://www.cnblogs.com/SFWR-YOU/p/10887284.html