2938: 骑士旅行
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 11 Solved: 3
[Status] [Submit] [Creator:]
Description
骑士每天的日子太枯燥了所以准备在棋盘上开启一次旅行，骑士行走的方式如下图所示。
请帮助骑士找出一条旅行路线使得每次骑士从棋盘上的一个点出发达到另外一个点，经过的方格都不同并且能够遍历整个棋盘
请帮助骑士找出一条旅行路线使得每次骑士从棋盘上的一个点出发达到另外一个点，经过的方格都不同并且能够遍历整个棋盘
Input
第一行一个整数N，表示测试数据的组数。
接下来N行，每行两个正整数p和q(1≤p*q<=26),表示是一个p*q的棋盘。其中p表示棋盘的行数，编号从1到p；q表示棋盘的列数，编号依次为A,B,C...
接下来N行，每行两个正整数p和q(1≤p*q<=26),表示是一个p*q的棋盘。其中p表示棋盘的行数，编号从1到p；q表示棋盘的列数，编号依次为A,B,C...
Output
对于每组测试数据：
第一行输出："Scenario #i",其中i表示测试数据的编号，i从1开始。
第二行输出一条满足条件的骑士旅行路径，如果存在多条请输出字典序最小的那条路径。如果不存在满足条件的路径请输出"impossible".
每两组测试数据之间用一个空行隔开。
第一行输出："Scenario #i",其中i表示测试数据的编号，i从1开始。
第二行输出一条满足条件的骑士旅行路径，如果存在多条请输出字典序最小的那条路径。如果不存在满足条件的路径请输出"impossible".
每两组测试数据之间用一个空行隔开。
Sample Input Copy
3
1 1
2 3
4 3
Sample Output Copy
Scenario #1:
A1
Scenario #2:
impossible
Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4