合肥学院
计算机科学与技术系
课程设计报告
2010～2011 学年第二学期
课学学专指
业导
班教生
姓
程 数据结构与算法
国王与骑士问题
王昆仑、张贯虹
名 号 级 师
课程设计题目名称
2011 年 6 月
一、课程设计名称及内容
名称：国王和骑士问题 内容：
初始状态：一个国王和N个骑士分布在8*8的棋盘上0 <= N <= 63 目标状态：国王和所有的骑士走到同一个格子里
游戏规则：在一次移动中，国王可以走到相邻的八个格子里；骑士可以走八个方向的“日”字；国王和某个骑士相遇后，可以由骑士带着移动。
要求：编写算法解决问题，用最少的总移动步数达到目标状态。
二、问题分析
本程序要求实现最短步数的计算，首先需要考虑8×8的棋盘的存储方式，以及各点的国王或骑士的表示方法，然后考虑最少步数的计算方法，最后通过各功能函数的调用解决问题。设计程序所能达到的功能：对一个国王与n个骑士会合在同一点的最少步数的计算。
1、数据的输入：
（1）需要输入的数据：①国王的坐标，②骑士的个数，③每个骑士的坐标；
（2）数据的类型与范围：坐标均为2个字符，横坐标为A~H中任意字符，纵坐标为1~8中任意字符，骑士个数须在0与64之间（不包括0、64）。
2、数据的输出：输出骑士与国王会合的最少步数、 3、测试数据：
（1）国王坐标：D4 骑士个数：4
每个骑士坐标：A3 A8 H1 H8 预计结果：最短步数为 10 （2）国王坐标：G1 骑士个数：3
每个骑士坐标：C3 A7 A5 预计结果：最短步数为 7 （3）国王坐标：F3 骑士个数：5
每个骑士坐标：A3 A5 B2 C5 D3 预计结果：最短步数为 9
三、概要设计
1、为了实现上述设计：需要：
（1）定义结点类型，分别表示棋盘上每个点的x，y坐标；
（2）设计遍历算法，因为国王与骑士最终可能在任意一点相遇，所以要求其最少步数，必须遍历棋盘上每一点，分别求出国王和骑士到每一点的步数，再进一步比较出其最小值；
（3）使用恰当搜索算法，由于骑士以“日”字型在棋盘上走动，要求其到达某一点的最短路径必须使用搜索算法，考虑遍历结点较多，采用广度优先搜索（BFS算法）；
（4）判断国王与骑士相遇及步数，由于一旦国王与骑士相遇，骑士便可以带着国王行动，所以必须比较在相遇与不相遇两种情况下的最少步数，得出最终答案；
2、本程序包含4个函数：
（1）主函数：main() （2）解题函数：solve()
（3）计算所有点骑士最少步数的函数：knightmindis()
（4）计算某两点间出发到某点骑士的最少步数的函数（包含BFS算法）：BFS() 各函数之间关系如下 ：
main() solve() knightmindis() BFS()
四、算法思想
国王与骑士位置均用坐标表示，因为只有一个国王，首先遍历国王至棋盘上每一点的最
短路径；又有n个骑士，分别遍历每个骑士至每一点的最短路径，并求它们的最短路径之和，同样要求最短，求国王与所有骑士的最短路径之和org。又由于存在情况骑士带着国王前进，故还要考虑国王与骑士相遇时的情况，便利骑士经过棋盘中每一点到另外每一点的步数，计算相遇时骑士带着国王前进的最短距离change，最后比较得到最终答案。
五、详细设计
实现概要设计中定义的数据类型，并对每个函数操作给出流程图、伪代码。 1、结点类型与定义
struct Pos{ //定义数据类型
int x,y; //x、y分别表示横纵坐标 };
2、定义全局变量
struct Pos king,knight[63]; //定义国王，骑士
int mindistance[8][8][8][8]; //任意两点之间骑士的最少步数 int knights; //骑士个数
int mindist=32767; //最少步数 3、流程图 开始 输入国王坐标 坐标处理 输入骑士个数 坐标处理 输入骑士坐标 输入次数<=骑士个数？ N 结束 (主函数) 调用解题函数 solve Y
数据结构与算法课程设计报告
