原题目：
Constraints
Time Limit: 1 secs, Memory Limit: 32 MB , Special Judge
Description
在一个8 * 8的棋盘中的某个位置有一只马，如果它走64步正好经过除起点外的其他
位置各一次，这样一种走法则称马的周游路线，试设计一个算法，从给定的起点出发，
找出它的一条周游路线。
为了便于表示一个棋盘，我们按照从上到下，从左到右对棋盘的方格编号，如下所示：
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
马的走法是“日”字形路线，例如当马在位置15的时候，它可以到达2、4、7、11、19、
23、26和28。但是规定马是不能跳出棋盘外的，例如从位置1只能到达9和14。
Input
输入有若干行。每行一个整数N(1<=N<=64)，表示马的起点。最后一行用-1表示结束，
不用处理。
Output
对输入的每一个起点，求一条周游线路。对应地输出一行，有64个整数，从起点开始按
顺序给出马每次经过的棋盘方格的编号。相邻的数字用一个空格分开。
算法思想及主要数据结构：
-
解题思想：采用 dfs 算法（深度优先搜索），考虑到时间复杂度问题，根据当前节点可到的节点数决定访问顺序。
-
主要数据结构：结构体保存节点值，vector保存所有有效节点，sort排序挑选下一个访问节点。
详细解题思路：
- 算法的选取。宽度优先搜索算法会把所有可能列出，浪费时间，采用深度优先搜索可以很好解决此问题。但是纯粹的DFS算法同样会超时，应适当剪枝。
- 剪枝。马的“日”字形走法有多种，有效的决定走哪个方向可以有效减少时间。显然，当当前可走的方向数越少分支会越少，这样就越容易到达目的地，为此，把下一个可能走的节点的可扩展的位置数保存起来，进行排序，优先走位置数少的节点。
- 马的移动分析：马必须走“日”字形，最多可走8个位置，把它化成二维数组帮助判断是否下一位置是否可走。
- 路径记录：一共走64步，用一维64个元素的数组记录，然后把刚才的二维数组转化为具体值。
- 每个当前位置，调用函数判断它下一个可走的位置数，把扩展的位置数以及当前的位置用结构体保存，把这些结构体保存至vector数据结构，然后排序用于选取下一要走的节点。
实现代码:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
bool visited[8][8];
int path[64]; //保存路径的各个节点
bool isOk;
//可以走的八个方向
int canMove[8][2] = {
{-2, 1}, {-2, -1},
{-1, 2}, {-1, -2},
{1, 2}, {1, -2},
{2, 1}, {2, -1}
};
//借助节点来判断每个节点可以往后走的方向数
struct node{
int x, y, weight;
node(int _x, int _y, int _weight) {
x = _x;
y = _y;
weight = _weight;
}
bool operator<(const node&n) const {
return weight < n.weight;
}
};
/*
*判断是否合理
*1、是否走出了方格
*2、是否访问过该节点
*/
bool isValid(int tx, int ty) {
if (tx >= 0 && ty >= 0 && tx < 8 && ty < 8
&& !visited[tx][ty])
return true;
return false;
}
//获取当前节点能够到达的方向总数
int getWeight(int x, int y) {
int weight = 0;
for (int i = 0; i < 8; i++) {
int tx = x+canMove[i][0];
int ty = y+canMove[i][1];
if (isValid(tx, ty))
weight++;
}
return weight;
}
/*深度搜索直到访问完所有节点为止*/
void dfs(int x, int y, int index) {
if (isOk) return;
if (index == 64) {
isOk = true;
cout << path[0];
for (int i = 1; i < 64; i++)
cout << " " << path[i];
cout << endl;
} else {
vector<node> temp;
for (int i = 0; i < 8; i++) {
int tx, ty;
tx = x+canMove[i][0];
ty = y+canMove[i][1];
if (isValid(tx, ty)) {
temp.push_back(node(tx, ty, getWeight(tx, ty)));
}
}
/*
*关键点(启发式)：
* 如果当前节点能够访问到下一个节点的数少的优先搜索
*/
sort(temp.begin(), temp.end());
for (int i = 0; i < temp.size(); i++) {
x = temp[i].x;
y = temp[i].y;
visited[x][y] = true;
path[index] = x*8+y+1;
dfs(x, y, index+1);
visited[x][y] = false;
}
}
}
int main() {
int t;
while (cin >> t && t != -1) {
memset(visited, 0, sizeof(visited));
path[0] = t;
isOk = false;
int x = (t-1)/8;
int y = (t-1)%8;
visited[x][y] = true;
dfs(x, y, 1);
}
return 0;
}