题目链接：http://vjudge.net/contest/view.action?cid=51369#problem/A （A - Children of the Candy Corn）
http://poj.org/problem?id=2488 （A Knight's Journey）
（不知道为什么，名字竟然不同哇~~~~还是poj 改名改得好）
题目意思：给出一个p * q 的棋盘，行用阿拉伯数字1,2，...，p-1, p 来表示，列从大写字母'A'开始表示。我这里为了简化问题，对于以下5 * 5 这个棋盘，可以把(1, B) 这个点看成是坐标(1, 2)，其他依此类推。不硬性规定要从哪个点开始，从哪个点结束，不过要把整个棋盘的每个点都要走过，按“日”字来走（玩过中国象棋的人一定很熟悉，就是马走“日”），如果不能把每个点都走过，就输出impossible，否则输出一条字典序最少的路径。
这个字典序最少真的是害人不少啊~~~而且，DFS 保存路径，我还是第一次接触，可能方法比较笨。为了按字典序最少来输出，很明显对于(3, 3)这个点来说，最先试探的应该是(2, 1) 这个点，其次是(4, 1)， 接着是（1， 2）， （5， 2），（1， 4）， （5， 4）， （2， 5）， （4， 5）。
红色字体的那部分表示相对于(3, 3) 这个中点来看，能走的8个点相对这个中点来说相差多少，假设要去(4, 1)这个点，（3，3) + (1, -2) ——> （4,1），所以设的8个方向可以到达的点不能乱来，是有顺序的！！！！
虽然写得比较长，不过是自己花了差不多4个小时做出来的（参考了自己以前写得一篇Knight Moves），也算是挺有成就感的^_^
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; const int maxn = + ;
int dx[] = {-, , -, , -, , -, }; // 这个设置不要乱了，字典序输出最少的关键啊~~~
int dy[] = {-, -, -, -, , , , };
int grid[maxn][maxn], route[maxn];
int p, q, flag, len; void dfs(int x, int y, int move, int len)
{
if (move == p*q) // 找到一条路径就不再找了(flag = 1, 使得dfs到此结束)
{
flag = ;
for (int i = ; i < len-; i++)
{
if (route[i])
{
if (i % == )
printf("%c", route[i]+'A'-); // route[0], route[2],...，route[2*n] 保存字母
else
printf("%d", route[i]); // route[1], route[3], ...，route[2*n-1] 保存数字
}
}
printf("%c%d\n", route[len-]+'A'-, route[len-]);
}
for (int i = ; i < && !flag; i++)
{
int tx = x + dx[i];
int ty = y + dy[i];
if (tx > && tx <= p && ty > && ty <= q && !grid[tx][ty]) // 在棋盘里面且没有走过
{
grid[tx][ty] = ;
route[len] = ty; // 不是tx！！看样例！！ 所以保存路径时要稍稍注意啦^_^
route[len+] = tx;
dfs(tx, ty, move+, len+);
grid[tx][ty] = ;
route[len] = ;
route[len+] = ;
}
}
} int main()
{
int t;
while (scanf("%d", &t) != EOF)
{
int cas = ;
while (t--)
{
scanf("%d%d", &p, &q);
printf("Scenario #%d:\n", ++cas);
flag = ;
for (int i = ; i <= p && !flag; i++)
{
for (int j = ; j <= q && !flag; j++)
{
memset(grid, , sizeof(grid));
memset(route, , sizeof(route));
flag = ;
len = ;
route[len] = i; // 假设可以从i, j，出发
route[len+] = j;
grid[i][j] = ; // i， j设为已走
dfs(i, j, , );
}
}
if (!flag)
printf("impossible\n");
printf("\n");
}
}
return ;
}
(今天暑假集训生活正式开始了，努力吧，+2)