练手CF3-C - Wormhouse

深搜,亮点在那个剪枝,flag代表是否搜索数组从开始到当前一直等于原始数组同位置的数,如果是真,就从原始数组的当前位置的书开始搜,否则就从0开始搜。

见代码。

#include <iostream>
#include <cstring> using namespace std;
int n,m,beg,origin[2003];
int mp[103][103];
bool vis[103][103];
int cnt;
int stk[2010];
bool check()
{
int i;
for(i=0;i<=m;i++)
{
if(stk[i]==origin[i])
continue;
if(stk[i]<origin[i])
return false;
if(stk[i]>origin[i])
return true;
}
return false;
} void dfs(int bg,bool flag)
{
// cout<<cnt<<endl;
if(cnt==m+1)
{
// for(int i=0;i<=m;i++)
// cout<<stk[i]<<' ';
// cout<<endl;
if(stk[cnt-1]==beg&&check())
{
return;
}
else
{
return;
}
}
for(int i=1;i<=n;i++)
{
if(flag&&i<origin[cnt])
continue;
if(mp[bg][i]&&!vis[bg][i])
{
vis[bg][i]=true;
vis[i][bg]=true;
stk[cnt++]=i;
dfs(i,flag&&i==origin[cnt-1]);
// cout<<stk[cnt]<<endl;
if(cnt==m+1&&stk[cnt-1]==beg&&check())
return;
// cout<<" "<<cnt<<endl;
cnt--;
// cout<<" "<<cnt<<endl;
vis[bg][i]=false;
vis[i][bg]=false;
}
}
return;
}
int main()
{
cin>>n>>m;
int i;
cnt=1;
memset(mp,0,sizeof(mp));
memset(vis,false,sizeof(vis));
cin>>origin[0];
beg=origin[0];
for(i=1;i<=m;i++)
{
cin>>origin[i];
mp[origin[i-1]][origin[i]]=1;
mp[origin[i]][origin[i-1]]=1;
}
//// for(i=1;i<=n;i++)
////// {
////// for(int j=1;j<=n;j++)
////// cout<<mp[i][j]<<' ';
////// cout<<endl;
//// }
stk[0]=beg;
dfs(beg,true);
// cout<<cnt<<endl;
if(cnt==m+1)
{
for(i=0;i<=m;i++)
cout<<stk[i]<<' ';
cout<<endl;
}
else
cout<<"No solution"<<endl;
return 0;
}

  

上一篇:2022.02.07 Day3


下一篇:剑指 Offer 29. 顺时针打印矩阵