先判斷這些單詞能不能構成 接龍 , 能的話在排序 , 然后深搜確定接龍 .?

題解 : 如果先確定所有單詞的首尾字母的個數 , 如果首字母個數等于尾字母個數就不用管了 , 如果發現首字母比尾字母大1那個這個單詞就是首位單詞 , 末尾單詞也是這樣確定 , 如果發現有兩個首尾的話 ?那么就不可能接龍成功 ?, ?如果成環的話 從字典序小的 單詞里面找一個字母 , 排序 , 開始深搜 ?, ?

1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #include<iostream> 5 #include<limits.h> 6 #include<algorithm> 7 #include<queue> 8 #include<vector> 9 #include<set> 10 #include<stack> 11 #include<string> 12 #include<sstream> 13 #include<map> 14 #include<cctype> 15 using namespace std; 16 struct node 17 { 18 char s[31]; 19 int first,last; 20 }a[1001]; 21 int n,degree_in[1001],degree_out[1001],order[1001],visited[1001]; 22 bool cmp(node a,node b) 23 { 24 return strcmp(a.s,b.s)<0; 25 } 26 int check() 27 { 28 int x1,x2,ans=0,i; 29 x1=x2=0; 30 for(i=0;i<26;++i) 31 { 32 if(abs(degree_in[i]-degree_out[i])>=2) 33 return -1; 34 else if(degree_in[i]-degree_out[i]==1) 35 x1++; 36 else if(degree_in[i]-degree_out[i]==-1) 37 { 38 x2++; 39 ans=i; 40 } 41 } 42 if(x1>1||x2>1) //當時三個度時，必定是 12 和21，相同的不能大于等于2，不然不能構成歐拉回路 43 return -1; 44 else if(x1==0) 45 { 46 for(i=0;i<26;++i) 47 if(degree_out[i]) 48 return i; //找到一個就行 49 } 50 else 51 return ans; 52 } 53 bool DFS(int st,int cnt) 54 { 55 int i; 56 if(cnt==n) 57 return 1; 58 for(i=0;i<n;++i) 59 { 60 if(a[i].first<st||visited[i]) 61 continue; 62 else if(a[i].first>st) 63 return false; 64 visited[i]=true; 65 order[cnt]=i; 66 if(DFS(a[i].last,cnt+1)) 67 return 1; 68 visited[i]=false;//回溯判斷是否形成歐拉路徑 69 } 70 return false; 71 } 72 int main() 73 { 74 int t; 75 scanf("%d",&t); 76 while(t--) 77 { 78 for(int i=0;i<1001;i++) 79 { 80 degree_in[i]=degree_out[i]=visited[i]=0; // 比 三個 memset 要快 81 } 82 scanf("%d",&n); 83 for(int i=0;i<n;i++) 84 { 85 scanf("%s",a[i].s); 86 int len=strlen(a[i].s); 87 a[i].first=a[i].s[0]-'a'; 88 a[i].last=a[i].s[len-1]-'a'; 89 degree_out[a[i].s[0]-'a']++; 90 degree_in[a[i].s[len-1]-'a']++; 91 } 92 int flag=check(); 93 if(flag==-1) 94 { 95 printf("***\n"); 96 continue; 97 } 98 sort(a,a+n,cmp); 99 if(!DFS(flag,0)) 100 { 101 printf("***\n"); 102 continue; 103 } 104 printf("%s",a[order[0]].s); 105 for(int i=1;i<n;i++) 106 printf(".%s",a[order[i]].s); 107 printf("\n"); 108 } 109 return 0; 110 }

?

?

?

轉載于:https://www.cnblogs.com/A-FM/p/5394324.html

總結

以上是生活随笔為你收集整理的单词拼接 ----- 深搜的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。