蓝桥杯备考-》单词接龙

很明显，这道题是可以用DFS来做的，我们直接暴力搜索，但是这里有很多点是我们需要注意的。

1.我们如何确定两个单词能接上？

比如touch和choose 应该合成为touchoose 

就是这样两个单词，我们让一个指针指着第一个字符串的末尾，一个指着开头，然后一个截取后面的子串，一个截取前面的子串，如果相等的话，就拼上

我们要截取的就是s1.substr(cur1)   和 s2.substr(0,cur2+1); 然后判断是否相等，如果相等的话就拼接上

2.我们如何避免 at连接atide这种情况呢？

我们截取子串的时候别截取到全部的就行，我们让cur1>=1 cur2<s2.size()-1

3.我们不能用全局的字符串，因为那样回溯的话很难回溯，我们应该把字符串放在参数了

4.我们定义一个cnt数组来给dfs剪纸，因为每个单词只能用两遍

5.我们不能直接传开头，那样的话都进不去dfs函数，我们要遍历一遍所有的字符串，找到开头一样的字符串进入dfs

好的，既然我们知道了所有的细节，我们来实现一下代码吧

#include <iostream>
using namespace std;
const int N = 30;
string s[N];
int n;
int cnt[N];
int ret = 0;
void dfs(string path)
{
	if(ret<path.size())
	{
		ret = path.size();
	}
	for(int i = 1;i<=n;i++)
	{
		if(cnt[i] >= 2) continue;
		int cur1 = path.size()-1;
		int cur2 = 0;
		while(cur1>=1 && cur2 < s[i].size()-1)
		{
			if(path.substr(cur1)==s[i].substr(0,cur2+1))
			{
				cnt[i]++;
				dfs(path+s[i].substr(cur2+1));
				cnt[i]--;
			}
			
			cur1--,cur2++;
		}
	}
}

int main()
{
	
cin >> n;
	for(int i =1;i<=n;i++)
	{
		cin >> s[i];
	}
	char ch ;cin >> ch;
	for(int i = 1;i<=n;i++)
	{
		if(s[i][0] == ch)
		{
			cnt[i]++;
			dfs(s[i]);
			cnt[i]--;
		}
	}
	
	cout << ret << endl;
	
	
	
	return 0;
}