本题是一个比较基础的DFS问题，但是坑点也有很多

1.字典序输出   2.如何处理输出过程中的字母的输出问题

AC后的恍然大悟：

本题要求的是棋盘的所有位置都必须经过一遍，且搜索是无方向性的。所以无论从哪个点开始，我们都必须经过每一点一次。（因此深搜只需一次）

而字典序最小的当然是从最左上角开始咯，我们只需要从(1,1)点开始深搜使所有点都被搜了一遍即可。如果无法搜完全部点，则impossible，否则输出

 

技巧：本题使用方向向量确定深搜的8个位置，注意，我们要将8个位置按照字典序大小排序，方便搜索时直接按序搜索即可

 

贴下AC代码：

#include<iostream>
#include<cstring>
using namespace std;

const int N = 30;
//方向向量
int dx[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
int dy[8] = {-2, -2, -1, -1, 1, 1, 2, 2};

//是否可以搜完的标志
bool flag;
//每达一点则该点被置为不可再被搜
bool st[N][N];

//每次搜索的点的位置表示
struct Path{
	char x;
	char y;
}path[N];

void dfs(int ux, int uy, int p, int q, int num){
	
	path[num].x = ux + '0';
	path[num].y = uy + 'A' - 1; 
	
	if(num == p * q){
		flag = true;
		return ;
	}
	
	for(int i = 0; i < 8; i++){ 
		int x = ux + dx[i], y = uy + dy[i];
		
		if(x > 0 && x <= p && y > 0 && y <= q && st[x][y] == false && flag == false){
			st[x][y] = true;
			dfs(x, y, p, q, num + 1);
			st[x][y] = false;
		
		}
	} 
}
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){	
		//每次新的测试数据的初始化 
		flag = false;
		memset(st, false, sizeof(st));
		st[1][1] = true;
		
		int p, q;
		cin >> p >> q;
		//从最左上角开始深搜
		dfs(1, 1, p, q, 1);
	
		cout << "Scenario #" << i << ":\n";
		
		if(flag){
			for(int j = 1; j <= p * q; j++) cout << path[j].y << path[j].x;
			cout << "\n";
		}
			
		else 
			cout << "impossible" << "\n";
 		
 		if(i != n) cout << "\n";
	} 
	return 0;
}