例题9.3A Knight's Jour

//DFS不难，想想也就能想明白了。但是要注意很多细节：每次都只是对当前情况做出改变，x\y坐标要重新定义新的
#include<iostream>
#include<cstring>
using namespace std;

int p;//行数 
int q;//列数
bool visit[27][27];

//int direction[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
int direction[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};//先数字方向，后字母方向 

bool DFS(int i,int j,int step,string str)//i\j先行后列 
{
if(step==q*p)
{
cout<<str<<endl<<endl;
return true;
}
else
{
for(int ii=0;ii<8;ii++)
{
int ni=i+direction[ii][0];//i+=direction[ii][0];不能写成这样。因为该方法只对当前情况进行改变，直接修改i、j会对所有情况造成影响 
int nj=j+direction[ii][1];//j+=direction[ii][1];
char col='A'+nj-1;//
char row='1'+ni-1;//
if(ni<1||ni>p||nj<1||nj>q||visit[ni][nj]==true)continue; //ninj

visit[ni][nj]=true;//仅仅是当前情况要修改 ninj
if(DFS(ni,nj,step+1,str+col+row))//ninj
{
return true;
}
visit[ni][nj]=false;//算过之后就到下一种情况了，还要改回来   ninj
}
}
return false;
}

int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
cin>>p>>q;
memset(visit,false,sizeof(visit));
cout<<&quot;Scenario #&quot;<<i<<&quot;:&quot;<<endl;
visit[1][1]=true;
if(DFS(1,1,1,&quot;A1&quot;)==false)
cout<<&quot;impossible&quot;<<endl<<endl;

}
    
}