熬夜完成 sicily1153 马周游解题报告。困死哥了.

唉!!! 上次交作业写错题目了,做了简单的马周游 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://blog.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
 
注意:如果起点和输入给定的不同,重复多次经过同一方格或者有的方格没有被经过,都会被认为是错误的。