C++实现单词接龙问题，求解最长“龙”的长度

以下是使用 C++ 实现单词接龙问题的代码： ```cpp #include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; // 检查两个单词是否可以相连，并返回重合部分的长度 int overlap(const string& a, const string& b) { for (int i = 1; i < min(a.size(), b.size()); ++i) { if (a.substr(a.size() - i) == b.substr(0, i)) { // 检查相邻两部分是否存在包含关系 if (a.size() < b.size() && a == b.substr(0, a.size())) continue; if (b.size() < a.size() && b == a.substr(a.size() - b.size())) continue; return i; } } return 0; } // 深度优先搜索函数，用于寻找最长的“龙” void dfs(const vector<string>& words, vector<int>& used, string current, int& maxLength) { maxLength = max(maxLength, static_cast<int>(current.size())); for (int i = 0; i < words.size(); ++i) { if (used[i] < 2) { int ol = overlap(current, words[i]); if (ol > 0) { used[i]++; dfs(words, used, current + words[i].substr(ol), maxLength); used[i]--; } } } } int main() { int n; cin >> n; vector<string> words(n); for (int i = 0; i < n; ++i) { cin >> words[i]; } char start; cin >> start; int maxLength = 0; vector<int> used(n, 0); for (int i = 0; i < n; ++i) { if (words[i][0] == start) { used[i]++; dfs(words, used, words[i], maxLength); used[i]--; } } cout << maxLength << endl; return 0; } ``` ### 代码解释： 1. **`overlap` 函数**：用于检查两个单词是否可以相连，并返回它们的重合部分的长度。在检查过程中，会排除相邻两部分存在包含关系的情况。 2. **`dfs` 函数**：深度优先搜索函数，用于寻找最长的“龙”。它会遍历所有可能的单词组合，并更新最长“龙”的长度。 3. **`main` 函数**：读取输入的单词和开头字母，然后对每个以开头字母开头的单词调用 `dfs` 函数，最后输出最长“龙”的长度。 ######[AI问答 | 670点数解答 | 2026-06-09 14:08:21]