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

骑士周游问题


回专题模式 回学习阶段模式 【题目名称、来源】 骑士周游问题(经典题目 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.


相关文章:
骑士周游详解
本来相练习一下用权值来解决这道经典的骑 士周游问题,没想到这道题用骑士周游的优化算法竟然超时(用自己的数据跑但是 oj 上是 AC 的),oj 上跑了 813ms 下面...
骑士周游问题
回专题模式 回学习阶段模式 【题目名称、来源】 骑士周游问题(经典题目 knight.pas) 【问题描述】 骑士周游问题 如下图所示,国际象棋棋盘上的马一步可以跳向八个...
骑士周游世界之快速周游
骑士周游世界之快速周游( **走一步看两步 走一步看两步** 骑士周游世界之快速周游(小于 1 秒)**走一步看两步** 【问题分析】 (1) 棋盘的表示方法 我们...
骑士周游
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 骑士周游 骑士周游骑士周游隐藏>> //骑士周游 骑士周游 #include<...
回溯法(马周游问题)——实验报告
回溯法(马周游问题)——实验报告_数学_自然科学_专业资料。回溯法(马周游问题)华南师范大学本科生实验报告 姓名_黎国庄_ 学号 20062101247 院系_计算机学院 专业_...
农夫过河和骑士周游(数据结构课程设计)
农夫过河和骑士周游(数据结构课程设计)_电脑基础知识_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 ...
高斯的确是神一般的存在
Gauss 可以在六步以内解决骑士周游问题。 Gauss 同时给 Bertrand Russell 和自己理发。 Gauss 想喝果汁时,直接对橙子使用夹挤定理。 Gauss 唱完 “Aleph-Null ...
更多相关标签:
骑士周游 | 骑士周游算法 | 八皇后问题 | 骑士周游问题 java | 骑士巡逻 | 骑士周游程序 | 骑士周游问题c | 骑士周游问题 欧拉 |