洛谷P1019|洛谷P1019 单词接龙洛谷P1019单词接龙

洛谷P1019 单词接龙题目描述单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beastbeast和astonishastonish，如果接成一条龙则变为beastonishbeastonish，另外相邻的两部分不能存在包含关系，例如atat 和 atideatide 间不能相连。
输入输出格式输入格式：输入的第一行为一个单独的整数 n n n ( n n n≤ \le ≤ 20) 表示单词数，以下n n n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出格式：只需输出以此字母开头的最长的“龙”的长度

输入样例：???????????????????????????输出样例:
5????????????????????????????????????23
at
touch
cheat
choose
tact
a

dfs
1.先找到有开头字母的那一个字符串咯（其实也就直接把那个字符当成一个字符串串了）
2.然后for循环遍历一遍，看有没有可以接上的，如果有的话就接上
3.接上之后要怎么办？？继续接嘛，一直接到接不了为止，然后再回溯，尝试另外的接法 嗷~~
4.每次接到不能接的时候会得到一个新的串串，这时更新答案。

#include #include> using namespace std; int ans = 0; int n; //ans为答案，n为输入的组数 const int maxn = 100; //n <= 20 string strs[maxn]; //储存每一组的字符串 string start; //开始的字符 int vis[maxn]; //标记字符串是否使用了两次 string result; //这是最终的最长字符串 bool can_be_connected(string s1,string s2,int k){//k越小(重叠部分越小)所得的长度越长 //把s2接到s1上面重复长度为k int len = s1.length(); //s1长度 for(int i = 0; i < k; i++){ if(s1[len-k+i] != s2[i])//判断重叠部分是否一样 return false; } return true; //如果都一样就返回true } void connect(string& s1,string s2,int k){ //把s2接到s1上面,重叠的长度为k string temp(s2,k,s2.length()-1); s1 += temp; } void dfs(string cur){//深搜 int cur_len = cur.length(); //获取当前组合的字符串的长度 ans = max(cur_len,ans); //更新ans for(int i = 1; i <= n; i++){//每一次都从头开始遍历看有没有符合条件的字符串 if(vis[i] == 2)//如果使用了两次就跳过 continue; int temp_len = strs[i].length(); //看当前的字符串(看能不能组合) for(int j = 1; j < temp_len; j++){ if(can_be_connected(cur,strs[i],j)){//如果能组合就组合 (j越小,所得长度越长) string temp = cur; connect(temp,strs[i],j); //组合 if(temp.length()>cur.length() && temp.length()>result.length())//如果有了更长的就把result更新 result = temp; if(temp == cur)//即为包含关系 continue; vis[i]++; //用过就++ dfs(temp); //继续找有没有能拼上的 vis[i]--; //回溯 } } } } int main() { cin >> n; for(int i = 1; i <= n; i++) cin >> strs[i]; cin >> start; dfs(start); cout << result << endl; cout << ans << endl; return 0; }

【洛谷P1019|洛谷P1019 单词接龙】PS:上面这段代码在洛谷可以A过去
但是有的编译器会运行出错(可能是没注意到溢出之类的问题)
还望dalao指正呀