回 帖 发 新 帖 刷新版面

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

在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个回复)

沙发

program horse;
const
  dx: array[0..8] of integer = (0, 1, 1, 2, 2, -1, -1, -2, -2);
  dy: array[0..8] of integer = (0, 2, -2, 1, -1, 2, -2, 1, -1);
var
  g: array[1..8, 1..8] of integer;
  n, m, x, y: integer;
  i, j, top: integer;
  stack: array[0..64] of integer;
begin
  assign(input, 'horse.in');
  reset(input);
  read(n, m);
  read(x, y);
  close(input);
  assign(output, 'horse.out');
  rewrite(output);
  for i := 1 to n do
    for j := 1 to m do
      g[i][j] := -1;
  g[x][y] := 0;
  sstack[0] := 0;
  top := 1;
  stack[top] := 0;
  while top > 0 do
  begin
    if top = n * m then
    begin
      for i := 1 to n do
      begin
        for j := 1 to m - 1 do
          write(g[i][j], ' ');
        writeln(g[i][m]);
      end;
      close(output);
      halt;
    end
    else
      inc(stack[top]);
      if (stack[top] > 8) then
      begin
        g[x][y] := -1;
        dec(top);
        x := x - dx[stack[top]];
        y := y - dy[stack[top]];
      end
      else
      begin
        x := x + dx[stack[top]];
        y := y + dy[stack[top]];
        if (x < 1) or (x > n) or (y < 1) or (y > m) or (g[x][y] <> -1) then
        begin
          x := x - dx[stack[top]];
          y := y - dy[stack[top]];
        end
        else
        begin
          g[x][y] := top;
          inc(top);
          stack[top] := 0;
        end;
      end;
  end;
  writeln('Impossible');
  close(output);
end.

板凳


谢谢,不过你要能找出我程序的问题就更好了!![em10][em10]

3 楼

我的程序怎么错了?
VAR
  map, map2: arr1;
  zx: arr2;
  step_a, step_i, step_j: arr3;
  n, p, q, i, j, a, lsi, lsj, step: INTEGER;
BEGIN
    READLN(n, p, q);
    i := p; j := q;
    a := 0;
    zx[1, 1] := -2; zx[1, 2] := -1;
    zx[2, 1] := -1; zx[2, 2] := -2;
    zx[3, 1] := 1; zx[3, 2] := -2;
    zx[4, 1] := 2; zx[4, 2] := -1;
    zx[5, 1] := -2; zx[5, 2] := 1;
    zx[6, 1] := -1; zx[6, 2] := 2;
    zx[7, 1] := 1; zx[7, 2] := 2;
    zx[8, 1] := 2; zx[8, 2] := 1;
    step := 0;
    REPEAT
         a := a + 1;
         IF a <= 8 THEN BEGIN
            lsi := i + zx[a, 1]; lsj := j + zx[a, 2];
            IF (lsi >= 1) AND (lsi <= n) AND (lsj >= 1) AND (lsj <= n) AND (map[lsi, lsj] = 0) THEN BEGIN
               i := lsi; j := lsj;
               step := step + 1;
               map2[i, j] := step;
               step_a[step] := a;
               map[i, j] := 1;
               step_i[step] := i; step_j[step] := j;
               a := 0;
            END;
         END ELSE BEGIN
            a := step_a[step];
            step := step - 1;
            i := step_i[step]; j := step_j[step];
         END;
    UNTIL step = n * n;
    FOR i := 1 TO n DO BEGIN
        FOR j := 1 TO n DO BEGIN
            WRITE(map2[i, j], ' ':5);
        END;
        WRITELN;
    END;
    READLN;
END.

4 楼

[color=000080][size=4]在你的程序里,加上些注释,即你的想法(算法),我们才容易看懂,才能帮你找出错,谢谢![/size][/color]

5 楼

[color=0000FF][size=4][size=3]matodied!你这人怎么这样!为什么我在任何地方发起这个寻找错误的帖子你都来凑热闹!!你可以自己发嘛,为什么发在人家的里面?我这个问题已经等了很久了,别人给你的答复很多了!![/size][/size][/color]

6 楼

怎么还没有人找到错误!!55555~~~~~~~~~~~

7 楼

PS:procedure init里的读入有问题:直接readln(n,p,q)就OK,如果按你这样只会读入n,p和q还等你输入数据......................

8 楼


不是拉,我是这样输入的(比如说我想让n=5,p=1,q=1):

5(enter)
1 1(enter)

9 楼

1 b[p1,q1]:=i;
  work(b,i+1,p1,q1);{寻找下一步(i+1)步,以p1,q1为起点}
  end
应该在end之前加b[p1,q1]:=0;(回朔,若不行则把它置为0以供下次递归用)

10 楼

abcwuhang:
1、注意看我的初始化过程init中,i的赋值是2,所以i表示的是当前正在试探的这一步(因为第一步就是p,q,用不再试探了)所以我觉应该是试探第sqn+1步了(实际上不存在),就终止
2、??上面刚刚对b[p1,q1]做了记号,将其赋值为i,为什么又是0??这不是………

我来回复

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