AcWing 1117. 单词接龙
原题链接
简单
作者:
soraplus
,
2024-07-24 14:57:27
,
所有人可见
,
阅读 2
#include<bits/stdc++.h>
using namespace std;
const int N = 21;
int n;
string word[N];
int g[N][N]; // 表示最短的后缀长度
int ans = 0;
int used[N]; // 编号为i的单词的使用次数
void dfs(string dragon, int last) {
ans = max((int)dragon.size(), ans); // 更新单词接龙的最大长度
used[last]++;
for (int i = 0; i < n; i++) {
if (g[last][i] > 0 && used[i] < 2) { // 确保有有效连接且单词未超限使用
dfs(dragon + word[i].substr(g[last][i]), i);
}
}
used[last]--;
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> word[i]; // 读取n个单词
}
char start;
cin >> start; // 读取开始的字母
// 填充邻接矩阵g
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
string a = word[i];
string 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;
}
}
}
}
// 从以start开头的单词开始进行DFS
for (int i = 0; i < n; i++) {
if (word[i][0] == start) {
dfs(word[i], i);
}
}
cout << ans << endl; // 输出单词接龙的最大长度
return 0;
}