主题:[讨论]骑士游历问题!!
在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.
感激!!
输入:
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.
感激!!