AcWing 1117. 单词接龙
原题链接
简单
作者:
no_one
,
2022-06-20 14:48:30
,
所有人可见
,
阅读 255
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 22;
int n;
int res = 0;
string word[N];
int used[N];
int g[N][N];
char start;
void dfs(string dra, int last)
{
res = max((int)dra.size(), res);
used[last] ++;
for(int i = 0; i < n ; i ++)
if(g[last][i] && used[i] < 2)
dfs(dra + word[i].substr(g[last][i]), i);
used[last] --;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> word[i];
cin >> start;
for(int i = 0; i < n; i ++)
for(int j = 0; j < n; j ++)
{
string a = word[i], b = word[j];
for(int k = 1; k < min(a.size(), b.size()); k ++)
if(a.substr(a.size() - k, k) == b.substr(0,k))
{
g[i][j] = k;
break;
}
}
for(int i = 0; i < n; i ++)
if(word[i][0] == start)
dfs(word[i], i);
cout << res << endl;
return 0;
}