程序设计类－跳马问题求解 [复制链接]

{回溯}pascal
在5*7的棋盘中,如下图
(horse1.in)
# # # # # # #
# # # # # # #
# # # # # # #
# # # # # # #
* # # # # # #

其中*为马，#为棋盘，求从左下角出发，要求走遍整个棋盘，使该马从右上方出去，并标名次序（如1，2，3，4，5……），起始点标明0；

需要注意的是，玩过中国象棋的人一定知道，马是走日字格的,此题也是如此，比如：
{1}
# # # # # # #
# # # # # # #
# # # # # # #
# # 1 # # # #
0 # # # # # #


!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!望有人能早日做出此题，小弟一定感激不尽~~~~~!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!![p:1]

没有人能做得出来吗?哭~~~~~~~~~~``````

问题不难，关键是要求什么，是所有路径还是最短路径？

其实也都很简单

是所有路径。大家快来做啊！

这~~~~跳马问题？

引用第4楼zhangkaili于2007-01-03 18:17发表的:
这~~~~跳马问题？

是啊?做得出来吗?

太简单了！！！

看饿的

跳马程序
EX6_16_2.PAS   EX6_16_1.PAS
问题描述：
在5*5格的棋盘上，从（1,1）点出发，按日字跳马，要求不重复地跳经所有方格。求出符合要求的所有跳马方案。
输出前5个方案及总方案数。（用回溯法实现）


输出格式示例：
1   16   21   10   25
20 11   24   15   22
17 2   19   6   9
12 7   4   23   14
3   18   13   8   5

EX6_16_2.PAS
var
a:array[1..5,1..5] of integer;   {记每一步走在棋盘的哪一格}
b:array[1..5,1..5] of boolean;   {棋盘的每一格有没有被走过}
u,v:array[1..8] of integer;     {8个方向上的x,y增量}
i,j,num:integer;

procedure print;       {打印方案}
var
k,kk:integer;
begin
  num:=num+1;           {统计总方案}
  if num<=5 then           {打印出前5种方案}
  begin
    for k:=1 to 5 do         {打印本次方案}
      begin
        for kk:=1 to 5 do   write(a[k,kk]:5);
        writeln;
      end;
  end;
end;
procedure try(i,j,n:integer);       {以每一格为阶段，在每一阶段中试遍8个方向}
var
k,x,y:integer;             {这三个变量一定要定义局部变量}
begin
if n>25 then begin
print;                   {达到最大规模打印、统计方案}
exit;
end ;  
for k:=1 to 8 do             {试遍8个方向}
begin
  x:=i+u[k]; y:=j+v[k] ;   {走此方向，得到的新坐标}
  if (x<=5) and (x>=1) and (y<=5) and (y>=1)and b[x,y] then   {如果新坐标在棋盘上，并且这一格可以走}
    begin
        b[x,y]:=false;   {有位子可走，置成false}
        a[x,y]:=n;     {该位子置成n，表示第n步已走好}
        try(x,y,n+1);   {从新的(x,y)去搜下一步该如何走}
        b[x,y]:=true;   {清空上一层，表示成没有用过}
        a[x,y]:=0;   {将该层置0}
    end;
end;
end;

begin
  u[1]:=1;   v[1]:=-2;         {8个方向的x,y增量}
  u[2]:=2;   v[2]:=-1;
  u[3]:=2;   v[3]:=1;
  u[4]:=1;   v[4]:=2;
  u[5]:=-1;   v[5]:=2;
  u[6]:=-2;   v[6]:=1;
  u[7]:=-2;   v[7]:=-1;
  u[8]:=-1;   v[8]:=-2;
  for i:=1 to 5 do         {初始化}
  for j:=1 to 5 do
    begin
      a[i,j]:=0;         {a数组清0}
      b[i,j]:=true;       {b数组置true，表示全部没用过}
    end;
  a[1,1]:=1;           从(1,1)第一步开始走}
b[1,1]:=false;         {A(1,1)已用，置成false}
  try(1,1,2);           {从(1,1)开始搜第2步该怎样走}
  writeln(num);         {输出总方案(304)}
end.