<p>
</p>
<p>
</p>
<p>
</p>
<h3 style="text-align: left; ">
<span style="font-size: 14px; ">简单的马周游问题</span>
</h3>
<p>
</p>
<p>
</p>
<p>
</center> </div>
<p>
</p>
<div>
</div>
<div>
<span style="font-size:14px;">Description</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">在一个5 * 6的棋盘中的某个位置有一只马，如果它走29步正好经过除起点外的其他位置各一次，这样一种走法则称马的周游路线，试设计一个算法，从给定的起点出发，找出它的一条周游路线。</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">为了便于表示一个棋盘，我们按照从上到下，从左到右对棋盘的方格编号，如下所示：</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">1 2 3 4 5 6</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">7 8 9 10 11 12</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">13 14 15 16 17 18</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">19 20 21 22 23 24</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">25 26 27 28 29 30</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">马的走法是“日”字形路线，例如当马在位置15的时候，它可以到达2、4、7、11、19、23、26和28。但是规定马是不能跳出棋盘外的，例如从位置1只能到达9和14。</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">Input</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">输入有若干行。每行一个整数N(1<=N<=30)，表示马的起点。最后一行用-1表示结束，不用处理。</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">Output</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">对输入的每一个起点，求一条周游线路。对应地输出一行，有30个整数，从起点开始按顺序给出马每次经过的棋盘方格的编号。相邻的数字用一个空格分开。</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">Sample Input</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">4</span>
</div>
<div>
<span style="font-size:14px;">-1</span>
</div>
<div>
<span style="font-size:14px;">Sample Output</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">注意：如果起点和输入给定的不同，重复多次经过同一方格或者有的方格没有被经过，都会被认为是错误的。</span>
</div>
<div>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">（1）原题中文大意</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">中国象棋的马按照象棋的规则在5 x 6 的棋盘上跑30步跑完所有的格子。</span>
</div>
<div>
</div>
<div>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">（2）算法思想及解题用到的主要数据结构</span>
</div>
<div>
</div>
<div>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">从每一个点往下走第二步，会有几点有效的行走位置。 把当前位置记在栈里面，以深度优先的方式进入下一个有效位置。如果下一个有效位置在之前已经走过，则从栈顶弹出上一位置，恢复到调出的位置后尝试未走过的有效位置。利用函数调用时会压栈的特别，用函数递归调用即可解决问题。</span>
</div>
<div>
</div>
<div>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">（3）详细解题思路</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">1. 先初始化一张表。这张表记下了棋盘上所有的30个位置的下一步可走的有效位置.</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">2. 写一个一般的递归调用自己的函数，表示马在走第几步时到了哪个位置，然后尝试走余下的所有可走位置。</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">3. 递归函数有两个退出条件。要么下一个要尝试的点已经走过了，要么走到了最后一步，即得解！</span>
</div>
<div>
</div>
<div>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">（4）逐步求精算法描述</span>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">用一个数组记下来经过的点。</span>
</div>
<div>
</div>
<div>
</div>
<div>
</div>
<div>
<span style="font-size:14px;">（5）程序注释清单</span>
</div>
<div>
</div>
<div>
<pre class="brush:cpp">#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>
using namespace std;
const static char row_num = 5; // 5行
const static char column_num = 6; // 6列
// 这个全局数组在初始化后会记下每30个有效位置的下一步可走位置.
// elocution[x][0]记个数。最多8个有效可走位置。
char elocution[30][9];
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;
}
// 增量数组.
char increments[8][2] =
{
1, -2, 2, -1, 2, 1, 1, 2,
-1, 2, -2, 1, -2, -1, -1, -2
};
// 得用增量数组来计算每一个位置的下一步有效位置。记到steps里面.
void next_step(char pos, char steps[])
{
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 > 4 || tmp._y < 0 || tmp._y > 5 )
{
continue;
}
serial_num = coordinate2serial_num(tmp);
if ( serial_num >= 1 && serial_num <= 30 )
{
valid_count++;
steps[valid_count] = serial_num;
}
else
{
cerr << “Not expected to reach here.\n”;
}
}
steps[0] = valid_count;
}
// 初始化记载所有点的下一步可走点的全局表。
void init_elocution()
{
for ( int i = 1; i <= 30; i++ )
{
next_step(i, elocution[i-1]);
}
}
char track[30]; // 记走过的路径.
bool quit_run_horse;
// 上文提高的递归函用函数.
void run_horse(char start_pos, char step_count)
{
if ( quit_run_horse ) // 用来快速退出深嵌套递归调用函数.
{
return;
}
for ( int i = 0; i < step_count; i++ )
{
// 已?经-经-过y这a点?了?.
if ( track[i] == start_pos )
{
return;
}
}
track[step_count] = start_pos; // 记下新走过的位置
if ( step_count == 29 ) // 最后一步则打印出结果。
{
for ( int i = 0; i < sizeof(track); i++ )
{
cout << (int)track[i];
if ( i + 1 != sizeof(track) )
{
cout << " “;
}
}
cout << endl;
quit_run_horse = true;
return;
}
for ( int i = 0; i < elocution[start_pos-1][0]; i++ )
{
run_horse(elocution[start_pos-1][i+1], step_count+1);
}
}
int main(int argc, char* argv[])
{
init_elocution();
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++ )
{
quit_run_horse = false;
run_horse(vec[i], 0);
}
return 0;
}