pascal走迷宫宽搜
来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/10/04 16:36:12
pascal走迷宫宽搜
已知一N×N的迷宫,允许往上、下、左、右四个方向行走,现请你找出一条从左上角到右下角的最短路径
行走顺序:右,下,左,上。
输入
输入数据有若干行,第一行有一个自然数N(N≤20),表示迷宫的大小,其后有N行数据,每行有N个0或1(数字之间没有空格,0表示可以通过,1表示不能通过),用以描述迷宫地图。从入口左上角(1,1)处,按照:右,下,左,上的行走顺序,走到出口在右下角(N,N)处。所有迷宫保证存在从入口到出口的可行路径。
输出
输出数据仅一行,为从入口到出口的最短路径(行走顺序:右,下,左,上)。路径格式参见样例
样例输入
4
0001
0100
0010
0110
样例输出
(1,1)->(1,2)->(1,3)->(2,3)->(2,4)->(3,4)->(4,4)
使用宽度有限搜索。
已知一N×N的迷宫,允许往上、下、左、右四个方向行走,现请你找出一条从左上角到右下角的最短路径
行走顺序:右,下,左,上。
输入
输入数据有若干行,第一行有一个自然数N(N≤20),表示迷宫的大小,其后有N行数据,每行有N个0或1(数字之间没有空格,0表示可以通过,1表示不能通过),用以描述迷宫地图。从入口左上角(1,1)处,按照:右,下,左,上的行走顺序,走到出口在右下角(N,N)处。所有迷宫保证存在从入口到出口的可行路径。
输出
输出数据仅一行,为从入口到出口的最短路径(行走顺序:右,下,左,上)。路径格式参见样例
样例输入
4
0001
0100
0010
0110
样例输出
(1,1)->(1,2)->(1,3)->(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,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<=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>=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;
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;
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.
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,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<=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>=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;
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;
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.
PASCAL 老鼠走迷宫问题
拼音,走迷宫,拼出一句话.
正义vs邪恶2.6迷宫怎么走啊
4年级下册暑假作业答案 走迷宫 读成语
走迷宫,一笔画完全图,且不允许重复.
走迷宫2012年江苏如果还有朋友们有这个问题,请搜索 走迷宫,读成语 我就是在哪知道的
第2大题 走迷宫,用笔画线路,拼出一句话.
什麽是右手定律?我说的是走迷宫时的右手定律啦..
pascal pascal pascal!
你知道穿珠和走迷宫的方法吗?讲一讲吐蕃大臣到唐朝求婚的故事
四年级下册暑假作业第33页走迷宫 读成语怎么做?各位大哥大姐谢啦
一个四则运算迷宫 从入口进去后可以按顺时针方向走,也可以按逆时针方向走.但必须在空格里添上"+-*/"号,使最后的运算结