回 帖 发 新 帖 刷新版面

主题:[讨论]骑士游历问题!!

在n*n的国际象棋棋盘的某一位置(p,q)有一个马,用“马走日字”的规则,要求它不重复地走完所有格子。
输入:
n p q
输出:
一个n*n的矩阵,表示每个格子是第几个走到。


我的程序怎么错了??

Program p260;
  type
     btype=array[1..100,1..100]of integer;
     atype=array[1..8,1..2]of integer;
  const a:atype=((-2,1),(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2));{马的八种走法}
  var
     n,sqn,i,k,p,q:integer;
     b:btype;{n*n的棋格}
  procedure work(b:btype;i,p,q:integer);{回溯法}
    var
       p1,q1,k:integer;
    procedure print;{打印过程}
      var
         i,j:integer;
      begin
         for i:=1 to n do
           begin
             for j:=1 to n do
               write(b[i,j],' ');
             writeln;
           end;
      end;
    begin
      if i=sqn+1 then begin print;halt;end;{如果全部走完就打印}
      k:=0;{列举马的八种走法}
      repeat
        inc(k);
        p1:=p+a[k,1];{p是起点横坐标,p1是新到位置}
        q1:=q+a[k,2];{q是起点纵坐标,q1是新到位置}
        if (p1>0)and(p1<=n)and(q1>0)and(q1<=n)and(b[p1,q1]=0) then begin{满足:这一点在棋盘上、没有走过}
              b[p1,q1]:=i;
              work(b,i+1,p1,q1);{寻找下一步(i+1)步,以p1,q1为起点}
                             end
      until (k=8);{无路可走,回溯}
      if i=2 then writeln('no solution!');{如果回溯到第二步仍无路可走,输出“不可能”}
    end;
  procedure init;
    begin
     readln(n);
     readln(p,q);
     sqn:=sqr(n);{表示总格子数}
     b[p,q]:=1;i:=2;
    end;
  begin
     init;
     work(b,i,p,q);
end.

感激!!

回复列表 (共24个回复)

21 楼

b[p1,q1]:=i;
work(b,i+1,p1,q1);{寻找下一步(i+1)步,以p1,q1为起点}

b[p1,q1]:=0;

end

原因:如果回溯失败那就要把之前尝试放的归0,以便下一步试放。。。


还有,在print函数里不要用for i变量,否则i会被打乱。。导致错误

22 楼

对了,1年了咋不见楼主回来?
怀念ing~~

23 楼

楼上,你的代码哪来的,根本不是这题吗!

24 楼

const
  maxm=30;
  maxn=30;
var
  m,n,x1,y1,x2,y2:longint;
  i,j,k,x,y:integer;
  map:array[-2..maxm+2,-2..maxn+2] of qword;
begin
  assign(input,'kinght.in');
  reset(input);
  assign(output,'kinght.out');
  rewrite(output);
  fillchar(map,sizeof(map),0);
  readln(m,n,x1,y1,x2,y2);
  map[y1,x1]:=1;
  for i:=y1+1 to y2 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[y2,x2]);
  close(input);
  close(output);
end.

我来回复

您尚未登录,请登录后再回复。点此登录或注册