当前位置:首页 >> 学科竞赛 >>

骑士周游问题


回专题模式 回学习阶段模式 【题目名称、来源】 骑士周游问题(经典题目 knight.pas) 【问题描述】 骑士周游问题 如下图所示,国际象棋棋盘上的马一步可以跳向八个方向,问:如果给出一个 n*m 的 棋盘,马从左上角开始跳,是否能够不重复的跳遍所有的格子。 输入:棋盘大小 n m 输出:n*m 个数,分 n 行 m 列,便利棋盘格子的顺序


>
源程序: 【所属专题】 【适合学习阶段】 【解题思路】 问题分析: 该问题是经典搜索问题 解答树: 2,3

1,1 3,2

1,5

3,5

4,4

3,4 存储结构: const direct:array[1..8,1..2] of integer= ((-2,1),(-1,2),(2,1),(1,2),(2,-1),(1,-2),(-1,-2),(-2,-1)); {马可以跳向八个方向的相对位移,使用常量数组可以将规则统一} Var a:array[1..10,1..10] of integer;{使用数组作为棋盘的存储, 如果某一格子没有走过值为 0, 否则为步数} 【测试数据】

【源程序】 program qishi;{Qi shi zhou you wen ti} const direct:array[1..8,1..2] of integer= ((-2,1),(-1,2),(2,1),(1,2),(2,-1),(1,-2),(-1,-2),(-2,-1)); {马可以跳向八个方向的相对位移,使用常量数组可以将规则统一} var n,m,x,y:integer; i,j,count:integer; a:array[1..10,1..10] of integer; procedure tiao(step,x,y:integer);{递归过程实现回溯} var r,i,j,k,l:integer;{r 是规则号,i,j 是按照 r 规则跳后的新位置} begin for r:=1 to 8 do begin i:=x+direct[r,1];j:=y+direct[r,2];{求新位置} if (i>=1)and(i<=n)and(j<=m)and(j>=1) then {如果新位置合法} if a[i,j]=0 then begin a[i,j]:=step; if step=n*m then begin{如果到达终点则打印} for k:=1 to n do begin for l:=1 to m do write(a[k,l]:3); writeln; end; close(output); halt; end else tiao(step+1,i,j);{如果没有到终点,跳下一步} a[i,j]:=0;{回溯} end; end; end; begin assign(input,'qishi.in'); reset(input); readln(n,m); {init} assign(output,'qishi.out'); rewrite(output); for i:=1 to n do for j:=1 to m do a[i,j]:=0; {初始化数组} a[1,1]:=1; tiao(2,1,1); writeln('Impossible'); close(output); end.


相关文章:
骑士周游
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 骑士周游 骑士周游骑士周游隐藏>> //骑士周游 骑士周游 #include<...
骑士周游世界之快速周游
骑士周游世界之快速周游( **走一步看两步 走一步看两步** 骑士周游世界之快速周游(小于 1 秒)**走一步看两步** 【问题分析】 (1) 棋盘的表示方法 我们...
农夫过河和骑士周游(数据结构课程设计)
农夫过河和骑士周游(数据结构课程设计)_电脑基础知识_IT/计算机_专业资料。文档内容有实验要求: 1.1实验目的 1.2实验内容问题描述 1.3:实验输出要求 2:程序设计...
旅行商问题
TSP 的历史很久,最早的描述是 1759 年欧拉研究的骑士周游问题,即对于国际象棋 棋盘中的 64 个方格,走访 64 个方格一次且仅一次,并且最终返回到起始点。 TSP 由...
TSP问题的概述
TSP 问题的由来 TSP 的历史很久,最早的描述是 1759 年欧拉研究的骑士周游问题,即对于国际 象棋棋盘中的 64 个方格,走访 64 个方格一次且仅一次,并且最终返回到...
旅行商问题
4、TSP 的历史很久,最早的描述是 1759 年欧拉研究的骑士周游问题,即对于国际象棋棋盘 中的 64 个方格,走访 64 个方格一次且仅一次,并且最终返回到起始点。TSP ...
2.旅行商TSP问题(1.1)
TSP 的历史很久,最早的描述是 1759 年欧拉研究的骑士周游问题,即对于 国际象棋棋盘中的 64 个方格, 走访 64 个方格一次且仅一次,并且最终返回到起 始点。 TSP...
运筹学学习心得体会
而此论文与范德 蒙德的一篇关于骑士周游问题的文章,则是继承了莱布尼茨提出的“位置分析” 的方法。 欧拉提出的关于凸多边形顶点数、棱数及面数之间的关系的欧拉...
数据结构课程设计贪心法求解TSP问题
TSP的历史很久,最早的描述是1759年欧拉研究的骑士周游问题,即对于国际象棋棋盘中 的64个方格,走访64个方格一次且仅一次,并且最终返回到起始点。类似的问题有: 中国...
算法分析实验
本题通过骑士周游问题,按照给你的走法,问骑士 能否在 p * q 的棋盘上,从某个点出发不重复走遍棋盘每个 点,如果能,输出骑士每步的位置(按字典序) ,如果不能...
更多相关标签:
骑士周游 | 骑士周游算法 | 八皇后问题 | 骑士周游问题 java | 骑士巡逻 | 骑士周游程序 | 骑士周游问题c | 骑士周游问题 欧拉 |