题解 | #A Knight's Journey#（DFS）

原题链接

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>

using namespace std;
const int maxn=28;
int p,q;
int trans[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};//八个方向转移
bool visit[maxn][maxn];//访问标记

bool dfs(int x,int y,int step,string s){//坐标、已遍历格子数、路径
  if(step==p*q){//遍历完成，输出
    cout<<s<<endl<<endl;
    return true;
  }
  for(int i=0;i<8;i++){
    int nx=x+trans[i][0];
    int ny=y+trans[i][1];
    char cx=nx+'0';//字符坐标
    char cy=ny+'A'-1;
    if(nx<1||ny<1||nx>p||ny>q||visit[nx][ny])continue;//越界或已访问过
    visit[nx][ny]=true;
    string next(s);
    next.insert(next.end(),cy);
    next.insert(next.end(),cx);
    if(dfs(nx,ny,step+1,next))return true;//递归
    visit[nx][ny]=false;//遍历失败，返回上层，取消标记
  }
  return false;
}
 int main(){
   int n;
   string s;
   while(scanf("%d",&n)!=EOF){
     int casenum=1;
     for(int i=0;i<n;i++){
       scanf("%d%d",&p,&q);
       memset(visit,false,sizeof(visit));
       cout<<"Scenario #"<<casenum++<<":"<<endl;
       visit[1][1]=true;
       if(dfs(1,1,1,"A1"))continue;
       else cout<<"impossible"<<endl<<endl;
     }
   }
   return 0;
 }