洛谷P1019单词接龙搜索

洛谷P1019 单词接龙
这道题目我用的是搜索
应为起点已经确认了，那就从这开始搜索，如果能接上去就接上去，回溯一下需要注意的就是一些细节问题，比方说不能被另一个单词完全覆盖等等以及字符串是从零开始的问题

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iomanip>
 8 #include <iostream>
 9 using namespace std ;
10 
11 int n,note[21],maxl ;
12 char a[21][301] ;
13 
14 inline bool can(int i,int j,int k) 
15 {
16     for(int p=0;p<=strlen(a[i])-j-1;p++) 
17         if(a[i][j+p]!=a[k][p]||p>=strlen(a[k])-1) return 0 ;   
18         //注意这里等于也要算进去 防止k串被覆盖 
19     return 1 ;  
20             
21 }
22 
23 inline void dfs(int i,int j,int l)     
24 //    i  表示当前末尾的串   j表示当前串与下一串是从i串的第 j个位置开始匹配的，注意开始的位置为0 
25 {
26     if(l>maxl) maxl = l ;
27     for(int k=1;k<=n;k++) 
28     {
29         if(note[k]<=1&&can(i,j,k) ) 
30         { 
31             note[ k ]++;
32             for(int len=1;len<=strlen(a[k])-1;len++)    //注意len 要从1开始枚举，因为该串不能被包含  
33                 dfs(k,len,l-strlen(a[i])+j+1-1+strlen(a[k])) ; //j是从零开始的    
34             note[ k ]-- ;
35         } 
36     }
37 }
38 
39 int main() 
40 {
41     scanf("%d",&n) ; 
42     for(int i=1;i<=n;i++) 
43         scanf("%s",a[i]) ;
44     scanf("%s",a[ 0 ]) ;
45     dfs(0,0,1) ;
46     printf("%d
",maxl) ;
47     return 0 ; 
48 }

洛谷P1019单词接龙 搜索

洛谷P1019单词接龙搜索