69 lines
2.0 KiB
C++
69 lines
2.0 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
const int N = 1010;
|
||
vector<string> str;
|
||
vector<int> path;
|
||
int n;
|
||
bool st[N];
|
||
|
||
/**
|
||
* 功能：爆搜，找出以u为起点，目前的长度是step,目标是找全n个字符串
|
||
* @param u 开始的字符串
|
||
* @param step 已经找完的字符串数量
|
||
* @return
|
||
*/
|
||
void dfs(int u, int step) {
|
||
//递归终止条件，这就是完成了任务，找到了一组
|
||
if (step == n) {
|
||
for (int i = 0; i < n; i++) {
|
||
cout << str[path[i]];
|
||
if (i + 1 < n) cout << '.'; //最后一个不输出.，只有前面n-1个输出.
|
||
}
|
||
exit(0);
|
||
}
|
||
//找出所有可能的下一步操作哪个字符串
|
||
for (int i = 0; i < n; i++) {
|
||
//如果当前字符串的尾字符（node[u].back()）与下一个字符串的首字符一样，并且没有使用过的话
|
||
if (!st[i] && str[u].back() == str[i][0]) {
|
||
path.push_back(i); //进入路径
|
||
st[i] = true; //使上
|
||
//递归
|
||
dfs(i, step + 1);
|
||
//回溯
|
||
st[i] = false;
|
||
path.pop_back();
|
||
}
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
//输入字符串
|
||
cin >> n;
|
||
string s;
|
||
for (int i = 0; i < n; i++) {
|
||
cin >> s;
|
||
str.push_back(s);
|
||
}
|
||
//排序
|
||
sort(str.begin(), str.end());
|
||
|
||
//从头开始，一个个尝试，看看哪个开头能跑完全程，找到第一个就退出
|
||
for (int i = 0; i < n; i++) {
|
||
//清空状态数组，方便下次尝试
|
||
memset(st, 0, sizeof st);
|
||
//记录路径上的第一个字符串
|
||
path.push_back(i);
|
||
//标识已使用，防止走回头路
|
||
st[i] = true;
|
||
//以i开头，进行爆搜
|
||
dfs(i, 1);
|
||
//回溯
|
||
st[i] = false;
|
||
path.pop_back();
|
||
}
|
||
//前面都没有成功，说明没有一个能打的~，那就输出***吧
|
||
cout << "***" << endl;
|
||
return 0;
|
||
} |