A Knight's Journey(騎士周遊)
1870 ワード
poj 2488
地図を与えて任意の位置から出発して、1本の経路を探し当てて、すべての地方を周遊することができます.
解决:dfs+遡及、この问题は更に深く遡及を理解して、しかし依然として知らないで、遍歴の顺番はどうしてこのようにして、もし谁が知っているならば、教えてください
このx,yは有効であり,再帰的x,yのみが有効な経路であるため,再帰関数に入ってすぐに記録する方法も提供される.
地図を与えて任意の位置から出発して、1本の経路を探し当てて、すべての地方を周遊することができます.
解决:dfs+遡及、この问题は更に深く遡及を理解して、しかし依然として知らないで、遍歴の顺番はどうしてこのようにして、もし谁が知っているならば、教えてください
このx,yは有効であり,再帰的x,yのみが有効な経路であるため,再帰関数に入ってすぐに記録する方法も提供される.
#include <iostream>
#include <bitset>
using namespace std;
int m,n;
int dx[]={-1,1,-2,2,-2,2,-1,1,};
int dy[]={-2,-2,-1,-1,1,1,2,2};
char res[900];
bool found;
bitset<30> b;
void tryIt(int p,int x,int y,int cnt)
{// , , x,y , res
res[p]=y+'A';
res[p+1]=x+'1';
if(cnt==m*n){res[p+2]='\0';found=true;}
// cout<<"this step is:"<<res[p]<<" "<<res[p+1]<<endl;
// show();system("pause");
if(found)return;
for(int i=0;i<8;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=0 && nx<m && ny >=0 && ny<n && b[nx*n+ny]==0)
{
b[nx*n+ny]=1;
tryIt(p+2,nx,ny,cnt+1);// found , return
if(found)return;
b[nx*n+ny]=0;
}
}
}
int main()
{
int icase;
cin>>icase;
for(int k=1;k<=icase;k++)
{
cin>>m>>n;
found=false;
for(int i=0;i<m && !found;i++)
for(int j=0;j<n && !found;j++)
{
b.reset();
found=false;
// ,
b[i*n+j]=1;
tryIt(0,i,j,1);
}
cout<<"Scenario #"<<k<<":"<<endl;
if(found)cout<<res<<endl;
else cout<<"impossible"<<endl;
cout<<endl;
}
system("pause");
return 0;
}