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

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

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

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


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

dfs+方向数组

饿补吧..

这么复杂啊
我还没有学到这个地步

牛人!!!

着道题本来不用这么麻烦的，我也做过的，我们竞赛班经常做的！
顶

easy!

var
a     : array[1..5,1..5] of integer;
b     : array[1..5,1..5] of boolean;
u,v   : array[1..8] of integer;
i,j,num : integer;

procedure print;
var
k,kk:integer;
begin
num:=num+1;
if num<=5 then begin
  for k:=1 to 5 do begin
    for kk:=1 to 5 do
    write(a[k,kk]:5);
    writeln;
    end;
    writeln;
  end;
end;

procedure try(i,j,n:integer);
var
k,x,y:integer;
begin
if n>25 then begin
  print;
  exit;
end ;
for k:=1 to 8 do 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;
    a[x,y]:=n;
    try(x,y,n+1);
    b[x,y]:=true;
    a[x,y]:=0;
  end;
end;
end;

begin
u[1]:=1; v[1]:=-2;
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;
    b[i,j]:=true;
  end;}
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),true);
a[1,1]:=1;
b[1,1]:=false;
try(1,1,2);
writeln(num);
readln;
end.

var
h : array[-1..7,-1..7] of integer;
a,b : array[1..8] of integer;
i,j,num : longint;

procedure print;
var
  i,j : integer;
begin
  num := num + 1;
  if num <= 5
    then begin
        for i := 1 to 5 do
          begin
          for j := 1 to 5 do
            write(h[i,j]:4);
          writeln;
          end;
        writeln;
        end;
end;

procedure try(x,y,i : integer);
var
  j,u,v : integer;
begin
  for j := 1 to 8 do
    begin
    u := x + a[j];
    v := y + b[j];
    if h[u,v] = 0
      then begin
          h[u,v] := i;
          if i < 25
            then
              try(u,v,i+1)
            else
              print;
          h[u,v] := 0;
          end;
    end;
end;

begin
for i := -1 to 7 do
  for j := -1 to 7 do
    if (i>=1) and (i<=5) and (j>=1) and (j<=5)
    then h[i,j] := 0
    else h[i,j] := 1;
a[1] := 2; b[1] := 1;
a[2] := 1; b[2] := 2;
a[3] := -1; b[3] := 2;
a[4] := -2; b[4] := 1;
a[5] := -2; b[5] := -1;
a[6] := -1; b[6] := -2;
a[7] := 1; b[7] := -2;
a[8] := 2; b[8] := -1;
num := 0;
h[1,1] := 1;
try(1,1,2);
writeln('num= ',num);
readln;
end.

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.