[Acwing] 1117. 单词接龙 dfs搜索顺序

前言

搜索顺序都给了。。 传送门 :

思路

从每个龙头开始枚举所有拼接可能

我们可以先处理出 所有字符串的最小公共长度 (因为答案是需要求最大拼接长度)

然后对每一个龙头做一遍 d f s dfs dfs , d f s dfs dfs就是拼接过程了,直接用 s u b s t r substr substr就行了,同时再

用 s t st st数组记录使用的次数就行了,最后回溯一下

CODE

int n,m,t;
int g[N][N];
int ans ;
int st[N];

void cal()
{

}
string w[N];


void dfs(string dragon,int last)
{
	ans = max((int)dragon.size(),ans);
	st[last] ++;
	
	for(int i = 0;in;
	for(int i = 0 ;i>w[i];
	
	char st;
	cin>>st;
	
	for(int i = 0;i