A Knight's Journey(騎士周遊)

1870 ワード

poj 2488
地図を与えて任意の位置から出発して、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;

}