P1019-单词接龙 - 从萌新到萌新的成长历程

题目传送门

题目思路

直接DFS搜就行了，注意匹配和坑

踩坑：首先可以自循环，如aabbaa，可以组合成aabbaabbaa，然后就是可能一个都不能组合，因此有人可能长度初始化为了0.。应该是最大的单个长度

AC代码

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

int ans = 0;
int n;

void DFS(vector<string> &words, vector<int> &v, int index, int len)
{
    if (v[index] >= 2)
        return;
    v[index]++;
    string t1 = words[index];
    for (int i = 0; i < n; i++)
    {
        if (v[i] >= 2)
            continue;
        string t2 = words[i];
        for (int j = max((int)(t1.length() - t2.length() + 1), 1); j < t1.length(); j++)
        {
            bool flag = true;
            int str = 0;
            for (int k = j; k < t1.length(); k++)
            {
                if (t1[k] != t2[str++])
                {
                    flag = false;
                }
            }
            if (flag)
            {
                len += t2.length() + j - t1.length();
                if (len > ans)
                {
                    ans = len;
                }
                DFS(words, v, i, len);
                len -= t2.length() + j - t1.length();
            }
        }
    }
    v[index]--;
}

int main()
{
    cin >> n;
    vector<string> words(n);
    for (int i = 0; i < n; i++)
    {
        cin >> words[i];
        if (words[i].length() > ans)
            ans = words[i].length();
    }
    char c;
    cin >> c;
    vector<int> visited(n, 0);
    for (int i = 0; i < n; i++)
        if (words[i][0] == c)
            DFS(words, visited, i, words[i].length());
    cout << ans << endl;
    return 0;
}