AcWing 4229. 哈密顿绕行世界问题
原题链接
简单
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int g[25][5],path[25];
int m,cnt;
bool visit[25];
void dfs(int x,int pos)
{
for(int i=1;i<=3;++i)
{
if(x==20 && g[pos][i]==m)
{
printf("%d: ",++cnt);
for(int i=1;i<=20;++i) printf("%d ",path[i]);
printf("%d \n",m);
return;
}
if(!visit[g[pos][i]])
{
visit[g[pos][i]]=1;
path[x+1]=g[pos][i];
dfs(x+1,g[pos][i]);
visit[g[pos][i]]=0;
}
}
}
int main()
{
for(int i=1;i<=20;++i)
{
scanf("%d%d%d",&g[i][1],&g[i][2],&g[i][3]);
if(!(g[i][1]<g[i][2] && g[i][2]<g[i][3]))
{
int a[3]={g[i][1],g[i][2],g[i][3]};
sort(a,a+3);
g[i][1]=a[0],g[i][2]=a[1],g[i][3]=a[2];
}
}
scanf("%d",&m);
while(m!=0)
{
memset(visit,0,sizeof visit);
cnt=0;
visit[m]=1;
path[1]=m;
dfs(1,m);
scanf("%d",&m);
}
return 0;
}