唉！！！ 上次交作业写错题目了，做了简单的马周游 sicily 1152。补上新的,应该是sicily 1153.为了解决规模太大的问题。加上了优化算法。
中大ACM实验题。
（1）原题中文大意
中国象棋的马按照象棋的规则在8 x 8 的棋盘上跑64步跑完所有的格子。
（2）算法思想及解题用到的主要数据结构
从每一个点往下走第二步，会有几点有效的行走位置。 把当前位置记在栈里面，以深度优先的方式进入下一个有效位置。如果下一个有效位置在之前已经走过，则从栈顶弹出上一位置，恢复到调出的位置后尝试未走过的有效位置。利用函数调用时会压栈的特别，用函数递归调用即可解决问题。
软之简单的马周游，8 x 8 棋盘的规模非常大。需要在可选下一步中找到最接近正确路线的点。求该点的办法是把所以的可选点先找出，再给这些可选点按权重排序，从最优的解依次向次优，次次优…..的点试探。重点在权重的算法。这里的权重的计算法则是指一个点的下一次可走的点的个数。
主要的数据结构有：
// elocution数组在初始化后会记下每个有效位置的下一步有哪些可走位
// 置.elocution[x][0]用下标0记个数。最多8个有效可走位置。
char elocution[ELEM_COUNT][9];
// stamps数组记每个点是否已经走过了。0表示没走过，1表示走过了。
char stamps[ELEM_COUNT];
// track数组记路径的顺序。
char track[ELEM_COUNT];
通过结合stamps数组和elocution数组可以算出下一步的每个点的权重。
（3）详细解题思路
1. 先初始化一张表。这张表记下了棋盘上所有的30个位置的下一步可走的有效位置.
2. 写一个一般的递归调用自己的函数，表示马在走第几步时到了哪个位置，然后求出余下的所有可走位置。
3. 余下的所有位置按照上文提到的权重排序。
4. 对于排序后的可选点数组，按顺序依次用递归函数尝试。
5. 递归函数有三个退出条件。1.下一个要尝试的点已经走过了，2.试完了所有的可选下一步无解。3.走到了最后一步，即得解！
（4）算法描述
初如化上文提到的elocution数组，清空stamps和tracks.从起点开始调用递归函数。
http://ykyi.net zausiu's blog.
（5）程序注释清单
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <csetjmp>
//#include <cassert>
using namespace std;
#define ROW_NUM 8
#define COLUMN_NUM 8
#define ELEM_COUNT ROW_NUM * COLUMN_NUM
jmp_buf jmpbuffer; // 很深的函数递归调用时用longjmp快速退出.
// elocution数组在初始化后会记下每个有效位置的下一步有哪些可走位
// 置.elocution[x][0]用下标0记个数。最多8个有效可走位置。
char elocution[ELEM_COUNT][9];
// stamps数组记每个点是否已经走过了。0表示没走过，1表示走过了。
char stamps[ELEM_COUNT];
struct coordinate // 二维坐标
{
char _x; // start from zero.
char _y;
};
// 作标转序号
char coordinate2serial_num(coordinate co)
{
char num = co._x * COLUMN_NUM + co._y + 1;
return num;
}
// 序号转坐标
coordinate serial_num2coordinate(char sn)
{
coordinate co;
co._x = (sn - 1) / COLUMN_NUM;
co._y = sn - co._x * COLUMN_NUM - 1;
return co;
}
// ((x:1;y:-2),(x:2;y:-1),(x:2;y:1),(x:1;y:2) (x:-1;y:2),(x:-2;y:1),(x:-2;y:-1),(x:-1;y:-2));
char increments[8][2] =
{
1, -2, 2, -1, 2, 1, 1, 2,
-1, 2, -2, 1, -2, -1, -1, -2
};
void next_step(char pos, char steps[]) // 把位置在pos序号的点的每一个下一个可选位置记在数组中。
{
char valid_count = 0;
coordinate co = serial_num2coordinate(pos);
coordinate tmp;
char serial_num;
for ( int i = 0; i < 8; i++ )
{
tmp._x = co._x + increments[i][0];
tmp._y = co._y + increments[i][1];
if ( tmp._x < 0 || tmp._x >= ROW_NUM || tmp._y < 0 || tmp._y >= COLUMN_NUM ) // 保证位置有效
{
continue;
}
serial_num = coordinate2serial_num(tmp);
if ( serial_num >= 1 && serial_num <= ELEM_COUNT )
{
valid_count++;
steps[valid_count] = serial_num;
}
else
{
cerr << "Not expected to reach here.\n";
}
}
steps[0] = valid_count;
}
// 下面的逻辑以每个点的下一步可跳点的数目作为权重排序。
struct pos_weight
{
char _pos;
char _weight;
};
// 又是用递归。这里为了实现快速排序
int partition(pos_weight poses[], int low, int high)
{
pos_weight pivot = poses[low];
while (low < high)
{
while (low < high && pivot._weight < poses[high]._weight)
high--;
poses[low] = poses[high];
while (low < high && pivot._weight >= poses[low]._weight)
low++;
poses[high] = poses[low];
}
poses[low] = pivot;
return low;
}
// 快速排序。
void quick_sort_steps(pos_weight poses[], int low, int high)
{
if ( low < high )
{
int pivot_loc = partition(poses, low, high);
quick_sort_steps(poses, low, pivot_loc-1);
quick_sort_steps(poses, pivot_loc+1, high);
}
}
void rearrage_steps(char poses[], int len) // poese里放置了下一个位置数组。Len是数组长度。
{
char weight, pos, next_step_count;
vector<pos_weight> vec(len);
for ( int i = 0; i < len; i++ ) // 计算权重.
{
weight = 0;
pos = poses[i];
next_step_count = elocution[pos-1][0];
for ( int j = 0; j < next_step_count; j++ )
{
char next_step_pos = elocution[pos-1][j+1];
if ( 0 == stamps[next_step_pos-1] )
{
weight++; // 如果有一下一跳点没走过则权重加1.
}
}
vec[i]._pos = pos;
vec[i]._weight = weight;
}
quick_sort_steps(&vec[0], 0, len-1); // 根据权重排序.
for ( int i = 0; i < len; i++ ) // 把排序后的位置写回原始数组.
{
poses[i] = vec[i]._pos;
}
}
void init_elocution()
{
memset(stamps, 0, sizeof(stamps));
for ( int i = 1; i <= ELEM_COUNT; i++ )
{
next_step(i, elocution[i-1]);
}
}
char track[ELEM_COUNT];
void run_horse(char start_pos, char step_count) // step_count [0 -- 64)
{
// 如果已经经过这点就立即退出函数。
if ( 1 == stamps[start_pos-1] )
{
return;
}
track[step_count] = start_pos;
if ( step_count == COLUMN_NUM * ROW_NUM - 1 ) // 是不是最后一步。
{
for ( int i = 0; i < sizeof(track); i++ )
{
cout << (int)track[i];
if ( i + 1 != sizeof(track) )
{
cout << " ";
}
}
cout << endl;
longjmp(jmpbuffer, 0x1);
return;
}
// 记下已经走了这一步。
stamps[start_pos-1] = 1; rearrage_steps(elocution[start_pos-1]+1, elocution[start_pos-1][0]);
for ( int i = 0; i < elocution[start_pos-1][0]; i++ )
{
run_horse(elocution[start_pos-1][i+1], step_count+1);
}
stamps[start_pos-1] = 0; // 试完了所有可走步.退出这个函数.重置这个位置为没有走过。
}
int main(int argc, char* argv[])
{
int pos;
vector<int> vec;
while(true)
{
cin >> pos;
if (pos==-1)
{
break;
}
vec.push_back(pos);
}
for ( int i = 0; i < vec.size(); i++ )
{
if(setjmp(jmpbuffer) == 0) // 为了很深的递归函数快速回退到这里。
{
init_elocution();
memset(track, 0, sizeof(track));
memset(stamps, 0, sizeof(stamps));
run_horse(vec[i], 0);
}
}
return 0;
}
（6）该算法的时间复杂度是 O(8 ^ (m * n)) m,n分别为棋盘的长和宽。
/////////////////// 原题目如下:
1153. 马的周游问题
Description
和题目C同样的任务，这里只是把棋盘扩大到标准的国际象棋。对这样一个8 * 8的棋盘用同样的方法编号如下：
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
Input
输入有若干行。每行一个整数N(1<=N<=64)，表示马的起点。最后一行用-1表示结束，不用处理。
Output
对输入的每一个起点，求一条周游线路。对应地输出一行，有64个整数，从起点开始按顺序给出马每次经过的棋盘方格的编号。相邻的数字用一个空格分开。
Sample Input
4
-1
Sample Output
注意：如果起点和输入给定的不同，重复多次经过同一方格或者有的方格没有被经过，都会被认为是错误的。