AcWing 1117. 单词接龙
原题链接
简单
作者:
我是java同学
,
2023-02-06 14:11:53
,
所有人可见
,
阅读 158
dfs
- 预处理,看每个单词是否能接在一个单词的后面,如果可以相互连一条边,与处理完后就可以爆搜,枚举所有情况
- 搜索深度为
40
(一个单词用两次)
- 拼的单词要长,那么重合的部分越短越好
g[][]
表示i
位置字符串和j
位置字符串拼接重合的最小长度
- 从给定的字符开始,确定单词龙的第一个单词,想所有能够拼接到的第一个单词后面的单词进行dfs
dfs(dragon,last)
:dragon
表示当前的单词龙,last
表示上一个连接到龙后面的单词
- substr有2种用法:
假设:string s = "0123456789"
;
- string sub1 = s.substr(5); //只有一个数字
5
表示从下标为5
开始一直到结尾:sub1 = "56789"
string sub2 = s.substr(5, 3);
//从下标为5
开始截取长度为3
位:sub2 = "567"
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 21;
int n;
string word[N];
int g[N][N];//判断每个单词是否有边(是否能拼接在一起)
int used[N];
int ans;
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] && used[i] < 2)
dfs(dragon + word[i].substr(g[last][i]), i);
used[last] -- ;//恢复现场
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> word[i];
char start;
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))
{//判断a的后k个字母和b的前k个字母是否一样
g[i][j] = k;//单词i和单词j的重合部分长度
break;
}
}
for (int i = 0; i < n; i ++ )
if (word[i][0] == start)
dfs(word[i], i);//记录当前龙的最后一个单词是第i个
cout << ans << endl;
return 0;
}