#include <iostream>
#include <queue>
#include <stack>
#include <cstring>
using namespace std;
/*广度优先搜索*/
/*将每个未访问过的邻接点进队列，然后出队列，知道到达终点*/
typedef class
{
public:
int x;
int y;
}coordinate;
int maze[][]; //迷宫
int road[][] = { { , - }, { , }, { -, }, { , } };
coordinate pre[][]; //记录当前坐标的前一个坐标
int visited[][] = { };
/*利用一个栈，倒序输出pre中存入的坐标*/
void print()
{
stack<coordinate> S;
coordinate rhs = { , };
while ()
{
S.push(rhs);
if (rhs.x == && rhs.y == )
break;
rhs = pre[rhs.x][rhs.y];
}
while (!S.empty())
{
rhs = S.top();
S.pop();
cout << "(" << rhs.x << ", " << rhs.y << ")" << endl;
}
}
void bfs(int x, int y)
{
queue<coordinate> Q; //用来帮助广度优先搜索
coordinate position;
position.x = x, position.y = y;
Q.push(position);
while (!Q.empty())
{
position = Q.front();
Q.pop();
visited[position.x][position.y] = ;
coordinate position2;
if (position.x == && position.y == ) //如果找到终点，停止搜索
{
print();
return;
}
for (int i = ; i < ; i++)
{
position2.x = position.x + road[i][];
position2.y = position.y + road[i][];
if (position2.x >= && position2.x <= && position2.y >= && position2.y <= && maze[position2.x][position2.y] == && !visited[position2.x][position2.y]) //如果这个邻接点不是墙且未访问过，则进队列
{
Q.push(position2);
pre[position2.x][position2.y] = position; //记录当前坐标的前一个坐标位置
visited[position2.x][position2.y] = ;
}
}
}
}
int main()
{
memset(maze, , sizeof(pre));
for (int i = ; i < ; i++)
for (int j = ; j < ; j++)
{
cin >> maze[i][j];
}
//memset(pre, 0, sizeof(pre)); //现将pre初始化
bfs(, );
return ;
}
#include <cstring>
#include<iostream>
using namespace std;
char route[][]; //记录行驶的路线
int board[][]; //棋盘
int total = ;
int length;
/*dfs深度优先搜索*/
int go[][] = { { -, - }, { , - }, { -, - }, { , - }, { -, }, { , }, { -, }, { , } };//字典序方向
/*一次跳跃*/
void knight(int p, int q,int len ,int row, int col) //len为行走的距离，用来判断是否遍历整个棋盘, row和col为当前坐标
{
board[row][col] = ;
route[len][] = col + 'A' - , route[len][] = row + '';
length = len;
/*让马分别尝试8个方向的跳跃，知道跳不动为止*/
int x, y;
for (int i = ; i < ; i++)
{
x = row + go[i][];
y = col + go[i][];
if (x > && x <= p && y > && y <= q && board[x][y] == )
knight(p, q, len + , x, y);
}
/*if (row - 1 >= 1 && col - 2 > 0 && board[row - 1][col - 2] == 0)
knight(p, q, len + 1, row - 1, col - 2);
if (row + 1 <= p && col - 2 > 0 && board[row + 1][col - 2] == 0)
knight(p, q, len + 1, row + 1, col - 2);
if (row - 2 >= 1 && col - 1 > 0 && board[row - 2][col - 1] == 0)
knight(p, q, len + 1, row - 2, col - 1);
if (row + 2 <= p && col - 1 > 0 && board[row + 2][col - 1] == 0)
knight(p, q, len + 1, row + 2, col - 1);
if (row - 2 >= 1 && col + 1 <= q && board[row - 2][col + 1] == 0)
knight(p, q, len + 1, row - 2, col + 1);
if (row + 2 <= p && col + 1 <= q && board[row + 2][col + 1] == 0)
knight(p, q, len + 1, row + 2, col + 1);
if (row - 1 >= 1 && col + 2 <= q && board[row - 1][col + 2] == 0)
knight(p, q, len + 1, row - 1, col + 2);
if (row + 1 <= p && col + 2 <= q && board[row + 1][col + 2] == 0)
knight(p, q, len + 1, row + 1, col + 2);*/
}
int main()
{
int N, p, q; //行数， 每次的宽和高
cin >> N;
while (N--)
{
cin >> p >> q;
knight(p, q, , , ); //以行走了0个单元
cout << "Scenario #" << ++total << ":" << endl;
if (length == p * q - )
{
for (int i = ; i <= length; i++)
cout << route[i][] << route[i][];
cout << endl << endl;
}
else
cout << "impossible" << endl << endl;
memset(board, , sizeof(board)); //清空棋盘的足迹
memset(route, , sizeof(route)); //清空路线
}
return ;
}