学步园

题意：给出一个国际象棋的棋盘（行为字母，列为数字，如:A1)。判断骑士（类似于马）能否不重复的走遍棋盘上的每一个点。若有多种方式，输出字典序最小的。
题解：

#include <iostream>
using namespace std;

bool check[30][30];
int p,q,counter;
int dir[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},{1, -2}, {1, 2}, {2, -1}, {2, 1}};

struct
{
	int a,b;
} path[900];

bool isOk ( int x, int y )
{
	if ( x < 1 || x > q || y < 1 || y > p || check[x][y] )
		return false;
	return true;
}

bool dfs ( int x, int y )
{
	check[x][y] = true;
	counter++;
	path[counter].a = x;
	path[counter].b = y;
	if ( counter == p*q )
		return true;
	int a,b;
	for ( int i = 0; i < 8; i++ )
	{
		a = x + dir[i][0];
		b = y + dir[i][1];
		if ( isOk(a,b) )
		{
			if ( dfs(a,b) )
				return true;
			check[a][b] = false;
			counter--;
		}
	}
	return false;
}

int main()
{
	int t;
	cin >> t;
	for ( int i = 1; i <= t; i++ )
	{
		cin >> p >> q;
		counter = 0;
		memset(check,0,sizeof(check));
		memset(path,0,sizeof(path));
		cout << "Scenario #" << i << ":" << endl;
		if ( dfs(1,1) )
		{
			for ( int j = 1; j <= p*q; j++ )
				cout << char(path[j].a + 'A' - 1 ) << path[j].b;
			cout << "\n\n";
		}
		else
			cout << "impossible" << "\n\n";
	}
	return 0;
}