作业帮 > 综合 > 作业

最短路径Pascal输入数据有若干行,第一行有一个自然数N(N≤20),表示迷宫的大小,其后有N行数据,每行有N个0或1

来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/05/04 12:24:30
最短路径Pascal
输入数据有若干行,第一行有一个自然数N(N≤20),表示迷宫的大小,其后有N行数据,每行有N个0或1(数字之间没有空格,0表示可以通过,1表示不能通过)用以描述迷宫地图。从入口左上角(1,1)处,按照下,上,左,右的行走顺序,走到出口在右下角(N,N)处。
输出数据仅一行,为从入口到出口的最短路径(行走顺序:下,上,左,右)。路径格式参见样例
输入
4
0001
0000
0010
0110
输出
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)
求各位大神帮帮忙解答一下,十分感谢!
尽量用深搜
type
intar=array[1..20,1..20] of shortint;
boolar=array[1..20,1..20] of boolean;
var
ch:array[1..20,1..20] of char;
n:integer;
a:intar;
b:boolar;
f:text;
i,j,stepnum,min:integer;
minpathstr:string;

procedure next(p,q,stepnum:integer;b:boolar;pathstr:string);
var
sp,sq:string[3]; 
s:string[20];
begin
if (p=n)and(q=n) then begin 
writeln(pathstr);
if stepnum<min then begin
min:=stepnum;
minpathstr:=pathstr;
{writeln(pathstr);}
end;
end
else begin
b[p,q]:=false;
if (b[p+1,q])and(a[p+1,q]<>1)and(p+1<=n) then begin 
str(p+1:0,sp); str(q:0,sq); s:='->('+sp+','+sq+')'; 
next(p+1,q,stepnum+1,b,pathstr+s);
end;
if (b[p,q+1])and(a[p,q+1]<>1)and(q+1<=n) then begin 
str(p:0,sp); str(q+1:0,sq); s:='->('+sp+','+sq+')'; 
next(p,q+1,stepnum+1,b,pathstr+s);
end;
if (b[p-1,q])and(a[p-1,q]<>1)and(p-1>=1) then begin 
str(p-1:0,sp); str(q:0,sq); s:='->('+sp+','+sq+')'; 
next(p-1,q,stepnum+1,b,pathstr+s);
end;
if (b[p,q-1])and(a[p,q-1]<>1)and(q-1>=1) then begin 
str(p:0,sp); str(q-1:0,sq); s:='->('+sp+','+sq+')'; 
next(p,q-1,stepnum+1,b,pathstr+s);
end;
end;  
end;

begin
assign(f,'最短路径.in'); reset(f);
readln(f,n);
for i:=1 to n do 
begin for j:=1 to n do read(f,ch[i,j]); readln(f); end;
close(f);
for i:=1 to n do for j:=1 to n do begin
a[i,j]:=ord(ch[i,j])-ord('0'); 
b[i,j]:=true;
end;
min:=32760;
minpathstr:='';
next(1,1,0,b,'(1,1)');
writeln;
writeln(min);
writeln(minpathstr);
end.