70pts,看样子是没法正确判断无解情况,求查错,代码带注释
  • 板块P1127 词链
  • 楼主Tangent233
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/10/24 11:38
  • 上次更新2023/11/5 10:01:31
查看原帖
70pts,看样子是没法正确判断无解情况,求查错,代码带注释
264548
Tangent233楼主2020/10/24 11:38
#include<bits/stdc++.h>
using namespace std;
int n;
string a[1010];
int cmp(string a,string b)
{
	int la=a.length(),lb=b.length();
	for(int i=0;i<min(la,lb);i++)
	{
		if(a[i]!=b[i]) return a[i]<b[i];
	}
	return la<lb;
}
vector<int> page[1010];
bool dis[1010],ok=0;
int lst[1010];
int p=1;
void print()
{
	for(int i=1;i<=n;i++)
	{
		cout<<a[lst[i]];
		if(i!=n) cout<<'.';
	}
}
void dfs(int s)
{
	if(!dis[s])
	{
		if(ok) return;
		dis[s]=1;
		lst[p]=s;
		p++;
		if(p>n)
		{
			print();
			ok=1;//遍历到了一个解就返回 
			return;
		}
		else for(int i=0;i<page[s].size();i++)
			dfs(page[s][i]);//接着遍历 
		dis[s]=0;
		lst[p]=0;
		p--;//回溯 
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n,cmp);//排序 
	for(int i=1;i<=n;i++)
	{
		int last=a[i].length()-1;
		for(int i1=1;i1<=n;i1++)
		{
			if(i1==i) continue;
			if(a[i][last]==a[i1][0]) page[i].push_back(i1);
		}
	}//建图 
	dfs(1);//遍历 
	if(!ok) cout<<"***";
	return 0;
}

2020/10/24 11:38
加载中...