合肥学院计算机科学与技术系
课程设计报告
2010～2011学年第二学期
课
程
数据结构与算法
课程设计题目名称学生姓名
国王与骑士问题
学
号
专业班级
指导教师
王昆仑、张贯虹
2011年6月
f一、课程设计名称及内容
名称：国王和骑士问题内容：初始状态：一个国王和N个骑士分布在88的棋盘上0N63目标状态：国王和所有的骑士走到同一个格子里游戏规则：在一次移动中，国王可以走到相邻的八个格子里；骑士可以走八个方向的“日”字；国王和某个骑士相遇后，可以由骑士带着移动。要求：编写算法解决问题，用最少的总移动步数达到目标状态。
二、问题分析
本程序要求实现最短步数的计算，首先需要考虑8×8的棋盘的存储方式，以及各点的国王或骑士的表示方法，然后考虑最少步数的计算方法，最后通过各功能函数的调用解决问题。设计程序所能达到的功能：对一个国王与
个骑士会合在同一点的最少步数的计算。
1、数据的输入：（1）需要输入的数据：①国王的坐标，②骑士的个数，③每个骑士的坐标；（2）数据的类型与范围：坐标均为2个字符，横坐标为AH中任意字符，纵坐标为18中任意字符，骑士个数须在0与64之间（不包括0、64）。2、数据的输出：输出骑士与国王会合的最少步数、3、测试数据：（1）国王坐标：D4
骑士个数：4每个骑士坐标：A3A8H1H8预计结果：最短步数为10（2）国王坐标：G1骑士个数：3每个骑士坐标：C3A7A5预计结果：最短步数为7（3）国王坐标：F3骑士个数：5每个骑士坐标：A3A5B2C5D3预计结果：最短步数为9
三、概要设计
1、为了实现上述设计：需要：（1）定义结点类型，分别表示棋盘上每个点的x，y坐标；（2）设计遍历算法，因为国王与骑士最终可能在任意一点相遇，所以要求其最少步数，必须遍历棋盘上每一点，分别求出国王和骑士到每一点的步数，再进一步比较出其最小值；（3）使用恰当搜索算法，由于骑士以“日”字型在棋盘上走动，要求其到达某一点的最短路径必须使用搜索算法，考虑遍历结点较多，采用广度优先搜索（BFS算法）；（4）判断国王与骑士相遇及步数，由于一旦国王与骑士相遇，骑士便可以带着国王行动，所以必须比较在相遇与不相遇两种情况下的最少步数，得出最终答案；2、本程序包含4个函数：
f（1）主函数：mai
（2）解题函数：solve（3）计算所有点骑士最少步数的函数：k
ightmi
dis（4）计算某两点间出发到某点骑士的最少步数的函数（包含BFS算法）：BFS各函数之间关系如下：
mai

solve
k
ightmi
dis
r