1、 计算机科学与技术系 课程设计报告 2010 2011 学年第 2 学期 课程课程 数据结构与算法 课程设计题目名称课程设计题目名称 马拦过河卒问题 学生姓名学生姓名 XXX 学号学号 XXX 专业班级专业班级 Xxx 指导教师指导教师 Xxx 2011 年 6 月 1、题目题目 名称：名称：马拦过河卒马拦过河卒问题问题 内容：内容： 棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。 同时在棋盘上 C 点有一个对方的马， 该马所在的点和所有跳跃一步可达的点称为对方马的控 制点。因此称之为“马拦过河卒”。 棋盘用坐标表示，A 点(0, 0)、B 点(n, m)
2、(n, m 为不超过 13 的整数)，同样马的位置坐标 是需要给出的。 要求计算出卒从 A 点能够到达 B 点的路径的条数， 假设马的位置是固定不动 的，并不是卒走一步马走一步。 2 2、问题分析、问题分析 图 1-1 坐标轴 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在 棋盘上的任一点有一个对方的马（如上图 1-1 的 C 点），该马所在的点和所有跳跃一步可达 的点称为方马的控制点。例如上图 C 点上的马可以控制 9 个点 （图中的 P1，P2.P8 和 C）。 卒不能通过对方的控制点。 棋盘用坐标表示，A 点（0，0）、B 点（n, m）(n,m 为不
3、超过 20 的整数，并由键盘输 入)，同样马 的位置坐标是需要给出的（约定：CA，同时 CB）。现在要求你计算出卒 从 A 点能够到达 B 点的路径的条数。做一个表，记录马可以攻击的位置，主要要包括马本身 的位置；然后从（0，0）开始每次递归（x+1,y）和（x，y+1） ，如何(x=n1 /查看马是否能够攻击到 if(c+1=0) /马不能在 y 坐标为 1 的点 if(d-1=0) ac-2d-1=0; if(d+1=0) /马不能在 y 坐标为 1 的点 if(d-1=0) ac-2d-1=0; if(d+1=Y) ac-2d+1=0; if(c+2=0) ac+2d-1=0; if(d+1=Y) ac+2d+1=0; fun(0,0); printf(“路径的条数为:“); printf(“%dn“,k); printf(“是否继续？0-退出n“); scanf(“%d“, if(s=0) break; return 0;
