最短路径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)
求各位大神帮帮忙解答一下,十分感谢!
尽量用深搜
输入数据有若干行,第一行有一个自然数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.
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.
最短路径Pascal输入数据有若干行,第一行有一个自然数N(N≤20),表示迷宫的大小,其后有N行数据,每行有N个0或1
c++ acm水题问题输入数据有多组,每组的第一行是两个整数m和n,表示应聘MM的总共的行列数,然后是m行整数,每行有n
pascal编程给出一个整数n,接下来有n行,每行一个整数r,表示圆的半径
有若干个自然数1、2、3.n连乘已知乘积末尾恰好有53个0,求n的最大值
每一幅图中有若干个大小不同的菱形,第一幅图中有1个,第二幅图中有3个,第3幅图中有5个,第n幅图中共有
pascal编程给出一个n,求前n个奇数的总和 输入 一行,一个整数n 输出 一行,表示总和
C++用栈解决括号匹配问题,要求第一行输入n表示有n个括号表达式需要判断,以下几行输入括号,
求n个数据中的最大值,并输出最大值是第几个,若最大值有多个相同,则输出最前面的一个.第一行输入n,
c语言如何输入整数N,代表下面有N组测试数据,接下来的N行,每行为一个整数?
vb,输入一个自然数n,求n!同时统计结果中有多少个0
c语言怎么写第一行是一个整数N,代表有N组测试数据,接下来是N行,每行有两个整数A和B.
输入数据有多组,每组占一行,每行的第一个数是整数n(n<100),表示需要统计的数