將一組單詞排列在一個列表，使得列表中任何單詞的首字母與其前面單詞的尾字母相同。輸入一個整數num（單詞個數），單詞數組char **arr，1<=num<=100，2<=各單詞長度<=100，且只包含小寫字母。若列表中的單詞可按照要求排列，返回1，否則，返回-1。如：a,[abcd,defg,ghij,jkl]輸出1
1 回答
當年話下
TA貢獻1890條經驗 獲得超9個贊
#include <iostream>
#include <vector>
#include <algorithm>
typedef pair<char,char> type;
bool dfs(vector<type> &a, char key)
{
if(a.empty())
{
return true;
}
else
{
int n=a.size();
for(int i=0;i<n;i++)
{
if(a[i].first==key)
{
auto tmp=a[i];
a.erase(a.begin()+i);
auto flag=dfs(a,tmp.second);
a.insert(a.begin()+i,tmp);
if(flag)
{
return true;
}
}
}
return false;
}
}
int main() {
vector<string> a={"abcd","hkl","dk","kj","jh"};
int n=a.size();
vector<type> a_pair;
for(auto t:a)
{
a_pair.push_back(make_pair(t.front(),t.back()));
}
bool flag=false;
for(int i=0;i<n;i++)
{
auto tmp=a_pair[i];
a_pair.erase(a_pair.begin()+i);
flag=dfs(a_pair,tmp.second);
a_pair.insert(a_pair.begin()+i,tmp);
if(flag)
break;
}
if(flag)
cout<<1;
else
cout<<-1;
return 0;
}
添加回答
舉報
0/150
提交
取消