P1019 单词接龙

 1 #include<iostream> 2 using namespace std; 3 int n,used[20]= {0},maxn=0; //n为单词数 used数组检测该单词是否已经被用多于两次（用++实现）  maxn表示最大长度 4 string s[20],sum,x; //s字符串数组为读入单词 sum为各个情况最后所形成的龙 x为开头字母 5 void dfs(string last) 6 { 7     if(last.size()==1) sum=last; //将开头字母看成上一个单词 用x初始化sum 8     bool ans=0; //表示接下来是否有符合要求的单词 9     for(int i=0; i<n; i++)10     {11         if(used[i]<2)12         {13             int m; //m为相同字母个数14             for(int j=last.size()-1; j>=0; j--) //从上一个单词的最后往前搜索15             {16                 if(last[j]==s[i][0])  //当该字母与当前单词首字母相同时17                 {18                     m=1;19                     ans=1; //有单词可接20                     while(last[j+m]==s[i][m]) m++; //记录相同字母数量21                 }22                 if(ans&&j+m==last.size()) break; //若该字母加上相同字母数量等于原单词长度 该单词可接23                 if(ans&&j+m!=last.size()) ans=0; //若不等 则ans恢复为0（即可能只是在上一个单词的中间出现与下一个单词相同的部分）24             }25             if(ans)26             {27                 int len=sum.size();28                 sum+=s[i].substr(m,s[i].size()-m); //在sum后面添加s[i]字符串第m(-1+1)个位置的s[i].size()-m个字符（下一个单词相同字母后的字母）29                 used[i]++; //使用次数增加30                 dfs(s[i]); //下一个单词搜索31                 ans=0; //恢复32                 used[i]--;33                 sum.erase(len,s[i].size()-m); //删去sum中len位置起的s[i].size()-m个字符(恢复原单词)34             }35         }36     }37     if(!ans&&sum.size()>maxn) maxn=sum.size(); //记录最大长度38     return;39 }40 int main()  //相信主程序so easy啦41 {42     cin>>n;43     for(int i=0; i<n; i++) cin>>s[i];44     cin>>x;45     dfs(x);46     cout<<maxn;47     return 0;48 }

 1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5  6 using namespace std; 7 const int N = 30; 8  9 int n,m,ans,c1,c2,size;10 int pd[N];11 char wd[N][N];12 char st;13 14 void dfs(int a,int len)15 {16     if(len>ans) ans = len;17     size = strlen(wd[a]);18     for(int k=size-1;k>=1;--k)19     {20         for(int i=1;i<=n;++i)21         {22             if(pd[i]==0) continue;23             c1 = k,c2 = 0;24             while(wd[a][c1]==wd[i][c2]&&c1<size) 25                 c1++,c2++;26             if(c2==strlen(wd[i])) continue;27             if(c2&&c1==size)28             {29                 pd[i]--;30                 dfs(i,len+strlen(wd[i])-c2);31                 pd[i]++;32             }33         }34     }35 }36 int main()37 {38     scanf("%d",&n);39     for(int i=1;i<=n;++i)40     {41         scanf("%s",&wd[i]);42         pd[i] = 2;43     }44     cin>>st;45     for(int i=1;i<=n;++i)46         if(wd[i][0]==st)47         {48             pd[i]--;49             dfs(i,strlen(wd[i]));50             pd[i]++;51         }52     printf("%d",ans);53     return 0;54 }