1220：单词接龙

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

【输入】

【输出】

【输入样例】

5
at
touch
cheat
choose
tact
a

【输出样例】

23

解析：深度优先搜索，详见代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int ans = 0;
string s[25];//s[i]:单词列表第i个单词
int vis[25];//vis[i]:单词s[i]用了几次
void dfs(string ls, int len) { //ls:当前龙中最后字符串,len为当前龙的长度
    ans = max(ans, len); //取可能的最大的长度
    for(int i = 1; i <= n; i++) {
        if(vis[i] < 2) { //只要用了不足2次
            //由于重合部分不能包含单词，所以重合部分长度要小于两单词的长度
            for(int j = 1; j < ls.length() && j < s[i].length(); j++) {
                //将ls末尾len个字符截取出来，看和s[i]前len个字符是否相同
                //只要找到一个可以接上的情况，就不再找了，再找到的不会是最长的龙
                if(ls.substr(ls.length() - j, j) == s[i].substr(0, j)) {
                    vis[i]++;//s[i]多用了1次
                    dfs(s[i], len + s[i].length() - j); //继续深搜
                    vis[i]--;//s[i]少用了1次
                    break;
                }
            }
        }
    }
}
int main() {
    char st;//起始字符
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    cin >> st;
    for(int i = 1; i <= n; i++) { //枚举每个单词
        if(s[i][0] == st) { //如果起始字符和s[i]首字符相同
            vis[i]++;//使用增加一次
            dfs(s[i], s[i].length()); //以s[i]起始深搜
            vis[i]--;//使用减少一次
        }
    }
    cout << ans;
    return 0;
}