主题:[讨论]骑士游历问题!!
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个回复)
11 楼
abcwuhang [专家分:1840] 发布于 2007-07-31 13:15:00
看我上面修改的.........
12 楼
cmy28 [专家分:380] 发布于 2007-07-31 13:23:00
哦,我试试…………
13 楼
abcwuhang [专家分:1840] 发布于 2007-07-31 14:50:00
如何?
14 楼
cmy28 [专家分:380] 发布于 2007-07-31 17:59:00
还那样,一点变化都没有。。[em10]
我觉得问题不在这里,你看,我过程里面b数组是[color=0000FF]数值参数[/color](前面没有var),那么递归回来以后,它不应该自己回到当前状态吗??
15 楼
cmy28 [专家分:380] 发布于 2007-08-04 11:25:00
有人么??[em6][em6]
16 楼
abcwuhang [专家分:1840] 发布于 2007-08-06 12:22:00
其实你的b数组已经是全局变量了,还要用来递归干什么!
把procedure work(b:btype;i,p,q:integer);的"b:btype;"删除,再把类似work(b,i,p,q);里面的"b,"去掉就ok了.
17 楼
cmy28 [专家分:380] 发布于 2007-08-08 21:45:00
不是这个意思,你不是说递归调用回来要b[p1,q1]:=0;吗?我把b放在形参表里面就是这个目的呀!!
18 楼
abcwuhang [专家分:1840] 发布于 2007-08-08 22:08:00
那你写:procedure work(VAR b:btype;i,p,q:integer);就可以了.
19 楼
cmy28 [专家分:380] 发布于 2007-08-13 14:52:00
…………不是…………无语…………
20 楼
pigone121 [专家分:10] 发布于 2007-08-17 16:08:00
const
x0:array[1..4]of shortint=(2,2,1,1);
y0:array[1..4]of shortint=(1,-1,2,-2);
var
n,m,x1,y1,x2,y2,i,j,k,x,y:integer;
f:array[1..50,1..50]of extended;
function ok(x,y:integer):boolean;
begin
if (x<=x2)and(y>=1)and(y<=m) then ok:=true
else ok:=false;
end;
begin
assign(input,'2.in');
assign(output,'2.out');
reset(input);
rewrite(output);
readln(n,m,x1,y1,x2,y2);
fillchar(f,sizeof(f),0);
f[x1,y1]:=1;
for i:=x1 to x2 do
for j:=1 to m do
if f[i,j]>0 then for k:=1 to 4 do
begin
x:=i+x0[k];
y:=j+y0[k];
if ok(x,y) then f[x,y]:=f[i,j]+f[x,y];
end;
writeln(f[x2,y2]:0:0);
close(input);
close(output);
end.
这是我做的[em1]
我来回复