很经典的搜索+最小字典序路径打印
巧妙的利用LAST结构体，来保存上一个节点的位置，最后再递归输出
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 30;
const int INF = 0x3f3f3f3f;int m, n;
bool vis[MX][MX];
int dist[][2] = {
{ -1, -2}, {1, -2}, { -2, -1}, {2, -1}, { -2, 1}, {2, 1}, { -1, 2}, {1, 2}};struct LAST {int x, y;
} La[MX][MX], End;bool DFS(int x, int y, int cnt) {if(cnt == m * n) {End.x = x;End.y = y;return true;}vis[x][y] = 1;for(int k = 0; k < 8; k++) {int nx = x + dist[k][0], ny = y + dist[k][1];if(nx < 1 || nx > m || ny < 1 || ny > n) continue;if(vis[nx][ny]) continue;La[nx][ny].x = x;La[nx][ny].y = y;if(DFS(nx, ny, cnt + 1)) {vis[x][y] = 0;return true;}}vis[x][y] = 0;return false;
}void print(int x, int y, int cnt) {if(cnt == m * n) {return;}print(La[x][y].x, La[x][y].y, cnt + 1);printf("%c%d", 'A' + y - 1, x);if(!cnt) printf("\n");
}int main() {int T, ansk = 0;scanf("%d", &T);while(T--) {memset(vis, false, sizeof(vis));End.x = -1;scanf("%d%d", &m, &n);bool sign = false;for(int j = 1; j <= n; j++) {for(int i = 1; i <= m; i++) {if(DFS(i, j, 1)) {sign = true;break;}}if(sign) break;}printf("Scenario #%d:\n", ++ansk);if(End.x != -1) {print(End.x, End.y, 0);} else {printf("impossible\n");}printf("\n");}return 0;
}