Question

pascal迷宫问题

时间限制:1秒 内存限制: 64 MB
试题描述
已知一N×N的迷宫，允许往上、下、左、右四个方向行走，现请你找出一条从左上角到右下角的最短路径。
输入要求
输入数据有若干行，第一行有一个自然数N（N≤20），表示迷宫的大小，其后有N行数据，每行有N个0或1（数字之间没有空格，0表示可以通过，1表示不能通过），用以描述迷宫地图。入口在左上角（1，1）处，出口在右下角（N，N）处。所有迷宫保证存在从入口到出口的可行路径。
输出要求
输出数据仅一行，为从入口到出口的路径（有多条路径时输出任意一条即可请严格按照 左 右 上 下）。路径格式参见样例。
输入样例
0001
0100
0010
0110
输出样例
(1,1)->(1,2)->(1,3)->(2,3)->(2,4)->(3,4)->(4,4)

Answer 1

const a:array[1..4]of integer=(0,1,0,-1);
b:array[1..4]of integer=(1,0,-1,0);
var g:array[0..21,0..21]of byte;
d:array[0..400,1..2]of integer;
f:array[0..400]of integer;
n,m,s1,s2,e1,e2,sum,h,t,i,j,x,y:integer;
c:char;
procedure Init;
begin
readln(n,m);
for i:=1 to n do begin
for j:=1 to m do begin
read(c);
if (c=48)or(c=49) then g[i,j]:=ord(c)-48
else if (c='R')then begin
s1:=i;
s2:=j;
g[i,j]:=0;
end else begin
e1:=i;
e2:=j;
g[i,j]:=0;
end;
end;
readln;
end;
procedure print(p,i:integer);
begin
if f[p]=1 then sum:=i
else print(f[p],i+1)
write('-(',d[p,1],',',d[p,2],')');
end;
procedure out;
write('(',s1,',',s2,')');
print(t,1);
writeln;
writeln(sum);
halt;
end.
begin
Init;
h:=0; t:=1; d[1,1]:=s1; d[1,2]:=s2;
f[h]:=0;
repeat
h:=h+1;
for i:=1 to 4 do begin
x:=d[h,1]+a[i];
y:=d[h,2]+b[i];
if g[x,y]=0 then begin
inc(t);
d[t,1]:=x; d[t,2]:=y; f[t]:=h;
g[x,y]:=1;
if (x=e1)and(y=e2)then out;
end;
end;
until t=h;
writeln;
writeln('0');
end.