View Code of Problem 1005

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#define Max 30

using namespace std;

int p,q;
int visit[Max][Max];
int dir[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};

int dfs(int x,int y,int step,string ans){
    if(step==p*q){
        cout<<ans<<endl<<endl;
        return 1;
    }
    else{
        for(int i=0;i<8;i++){
            int x1=x+dir[i][0];
            int y1=y+dir[i][1];
            char ans1=y1+'A';
            char ans2=x1+'1';
            if(x1>=0&&y1>=0&&x1<p&&y1<q&&visit[x1][y1]==0){
                visit[x1][y1]=1;
                if(dfs(x1,y1,step+1,ans+ans1+ans2))
                    return 1;
                visit[x1][y1]=0;
            }
        }
        return 0;
    }
}

int main(){
    int n,no=0;
    cin>>n;
    while(n--){
        no++;
        memset(visit,0,sizeof(visit));
        visit[0][0]=1;
        cin>>p>>q;
        cout<<"Scenario #"<<no<<":"<<endl;
        if(dfs(0,0,1,"A1")==0)
            cout<<"impossible"<<endl<<endl;
    }
    return 0;
}