题目描述
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8×88 \times 88×8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?
输入
The input begins with a positive integer nnn in the first line. The following lines contain nnn test cases. Each test case consists of a single line with two positive integers ppp and qqq, such that 1≤pq≤261 \le pq \le 261≤pq≤26. This represents a p×qp \times qp×q chessboard, where ppp describes how many different square numbers exist, qqq describes how many different square letters exist. These are the first qqq letters of the Latin alphabet.
输出
The output for every scenario begins with a line containing Scenario #i:, where iii is the number of the scenario starting at 111. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.
If no such path exist, you should output impossible on a single line.
输入输出样例
样例输入 #1
3
1 1
2 3
4 3样例输出 #1
Scenario #1:
A1
Scenario #2:
impossible
Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4
#include<bits/stdc++.h>
using namespace std;
const int N=2020;
int n,m,cnt=1;
int dx[8]={-2,-2,-1,-1,1,1,2,2},dy[8]={-1,1,-2,2,-2,2,-1,1};//这里讲一下为什么是这个顺序
//:其实某位大佬说过,dfs输出字典序,无非就是按顺时针搜索,或者以字典序最小的那个开始搜,到最后搜出来的一定是最小
//int go[8][2] = { {-2,-1},{-2, 1}, {-1,-2},{-1,2}, {1,-2},{1,2},{2,-1},{2,1}};
struct node
{
int x,y;
string s;
}k[50];
bool vis[N][N],f;
void dfs(int x,int y,int num)
{
if(f) return;
k[num].x=x,k[num].y=y;
if(num==n*m)
{
cout<<"Scenario #"<<cnt++<<":"<<endl;
for(int i=1;i<=n*m;i++) printf("%c%d",k[i].x-1+'A',k[i].y);
f=true;
cout<<endl;
}
for(int i=0;i<8;i++)
{
int x1=x+dx[i],y1=y+dy[i];
if(x1>0&&x1<=n&&y1>0&&y1<=m&&!vis[x1][y1]&&!f)
{
vis[x1][y1]=true;
dfs(x1,y1,num+1);
vis[x1][y1]=false;
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
f=false;
memset(vis,false,sizeof vis);
cin>>m>>n;
vis[1][1]=true;
dfs(1,1,1);
if(!f) cout<<"Scenario #"<<cnt++<<":"<<endl<<"impossible"<<endl<<endl;
}
return 0;
}