返回顶部

收藏

Pascal经典算法详解 - 骑士游历问题

更多

输入: m,n,x1,y1,x2,y2 (分别表示m,n、起点坐标和终点坐标) 输出: 路径数目(若不存在,则输出0) 【分析】 本题可以使用深度搜索发求解,但是效率很低,当路径很多时,不可能在短时间内出解。可以采用动态规划的设计思想。 从(x1,y1)位置出发,按照由左到右的顺序定义阶段的方向。位于(x2,y2)的左方且可达(x2,y2)的跳马位置集合都是(x2,y2)的子问题,起点至(x2,y2)的路径数实际上等于起点至这些位置集的路径数之和。可以按照阶段的顺序依次计算每一个阶段每个点的路径数目。 阶段i:中国象棋马当前的列位置(x1≤i≤x2) 状态j:中国象棋马在i列的行位置(1≤i≤m) 状态转移方程map[i,j]:起点(x1,y1)至(i,j)的路径数目 具体算法如下:

fillchar(map,sizeof(map),0);
map[x1,y1]←1;
for i←x1+1 to x2 do
  for j←1 to m do
     map[i,j]←map[i-1,j-2]+map[i-1,j+2]+map[i-2,j-1]+map[i-2,j+1];
writeln(map[x2,y2]);

                                详细代码:
program qishiyouli;
const
  maxm=50;
  maxn=50;
var
  m,n,x1,y1,x2,y2:integer;
  i,j,k,x,y:integer;
  map:array[-2..maxm+2,-2..maxn+2] of extended;
begin
fillchar(map,sizeof(map),0);
readln(m,n,x1,y1,x2,y2);
map[x1,y1]:=1;
for i:=x1+1 to x2 do
  for j:=1 to m do
      map[i,j]:=map[i-1,j-2]+map[i-1,j+2]+map[i-2,j-1]+map[i-2,j+1];
writeln(map[x2,y2]:0:0);
end.

标签:骑士游历,算法,Pascal

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. Yu Feng 发表 2013-03-01 14:01:11 开源压缩算法Zopfli介绍
  2. abcd9.com 发表 2013-03-06 01:02:01 迭代算法与递归算法
  3. 潘魏增 发表 2012-02-01 13:22:36 潘采夫女儿的数学题解法
  4. IT路人 发表 2013-05-02 15:01:58 Object-C:通过Luhn算法验证信用卡卡号是否有效
  5. Era 发表 2013-06-14 01:21:58 百度算法调整,外链应怎么做?
  6. 豆瓣电影 发表 2013-07-04 03:34:31 算法工程师如何改进豆瓣电影 TOP250
  7. 博主 发表 2013-08-15 05:32:06 常用排序算法小结
  8. 博主 发表 2013-09-07 16:58:19 Reddit 排名算法工作原理
  9. admin 发表 2013-11-25 08:14:29 堆排序代码举例
  10. 锦轩 发表 2014-03-20 06:31:32 反转比特位(文章最后有干货)
  11. klion26 发表 2014-01-07 05:31:36 二叉树的非递归遍历
  12. 0X55AA 发表 2014-05-17 04:52:04 llvm clang编译

发表评论