蓝桥杯算法训练VIP-单词接龙 就离谱

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
// 定义字符串数组，用于存储输入的字符串
string s[30];
// 定义整型数组和变量，用于记录状态和最大长度
int aa[30], n, kkk;
int f(string a, string b) {
    // 获取两个字符串的长度
    int la = a.size(), lb = b.size();
    // 计算两个字符串中较短的长度
    int ll = min(la, lb);
    int ss;
    // 遍历所有可能的重叠长度
    for (int i = 1; i < ll; i++) {
        ss = 1;
        // 检查当前长度的重叠部分是否匹配
        for (int j = 0; j < i; j++) {
            if (a[la - i + j] != b[j]) {
                ss = 0;
            }
        }
        // 如果找到匹配的重叠部分，返回其长度
        if (ss) {
            return i;
        }
    }
    // 如果没有找到匹配的重叠部分，返回0
    return 0;
}
void dfs(string t, int l) {
    // 更新最大长度
    kkk = max(kkk, l);
    // 遍历所有字符串
    for (int i = 1; i <= n; i++) {
        // 如果当前字符串已经被使用两次，跳过
        if (aa[i] >= 2) {
            continue;
        }
        // 计算当前字符串与拼接字符串的重叠部分长度
        int k = f(t, s[i]);
        // 如果存在重叠部分
        if (k > 0) {
            // 标记当前字符串已被使用一次
            aa[i]++;
            // 递归调用dfs函数，继续拼接字符串
            dfs(s[i], l + s[i].size() - k);
            // 回溯，取消当前字符串的使用标记
            aa[i]--;
        }
    }
}
int main() {
    // 读取字符串的数量
    cin >> n;
    // 读取每个字符串并存储到数组中
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    // 读取初始拼接字符串
    string c;
    cin >> c;
    // 调用dfs函数，开始深度优先搜索
    dfs(' ' + c, 1);
    // 输出最大拼接字符串的长度
    cout << kkk << endl;
    return 0;
}