主题:[讨论]骑士游历问题!!
cmy28
[专家分:380] 发布于 2007-07-20 13:24:00
在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.
感激!!
最后更新于:2007-07-21 10:47:00
回复列表 (共24个回复)
沙发
bigchen [专家分:1940] 发布于 2007-07-20 16:20:00
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.
板凳
cmy28 [专家分:380] 发布于 2007-07-20 16:26:00
谢谢,不过你要能找出我程序的问题就更好了!![em10][em10]
3 楼
Matodied [专家分:7560] 发布于 2007-07-20 21:34:00
我的程序怎么错了?
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 楼
怜丹欣∮ [专家分:120] 发布于 2007-07-21 08:44:00
[color=000080][size=4]在你的程序里,加上些注释,即你的想法(算法),我们才容易看懂,才能帮你找出错,谢谢![/size][/color]
5 楼
cmy28 [专家分:380] 发布于 2007-07-21 10:40:00
[color=0000FF][size=4][size=3]matodied!你这人怎么这样!为什么我在任何地方发起这个寻找错误的帖子你都来凑热闹!!你可以自己发嘛,为什么发在人家的里面?我这个问题已经等了很久了,别人给你的答复很多了!![/size][/size][/color]
6 楼
cmy28 [专家分:380] 发布于 2007-07-30 18:18:00
怎么还没有人找到错误!!55555~~~~~~~~~~~
7 楼
abcwuhang [专家分:1840] 发布于 2007-07-30 21:59:00
PS:procedure init里的读入有问题:直接readln(n,p,q)就OK,如果按你这样只会读入n,p和q还等你输入数据......................
8 楼
cmy28 [专家分:380] 发布于 2007-07-30 22:22:00
不是拉,我是这样输入的(比如说我想让n=5,p=1,q=1):
5(enter)
1 1(enter)
9 楼
abcwuhang [专家分:1840] 发布于 2007-07-31 12:30:00
1 b[p1,q1]:=i;
work(b,i+1,p1,q1);{寻找下一步(i+1)步,以p1,q1为起点}
end
应该在end之前加b[p1,q1]:=0;(回朔,若不行则把它置为0以供下次递归用)
10 楼
cmy28 [专家分:380] 发布于 2007-07-31 13:00:00
abcwuhang:
1、注意看我的初始化过程init中,i的赋值是2,所以i表示的是当前正在试探的这一步(因为第一步就是p,q,用不再试探了)所以我觉应该是试探第sqn+1步了(实际上不存在),就终止
2、??上面刚刚对b[p1,q1]做了记号,将其赋值为i,为什么又是0??这不是………
我来回复