关于pascal的几道题目

问题描述：

关于pascal的几道题目
走迷宫（Maze）【问题描述】已知一N×N的迷宫,允许往上、下、左、右四个方向行走,现请你找出一条从左上角到右下角的最短路径. 【输入数据】输入数据有若干行,第一行有一个自然数N（N≤20）,表示迷宫的大小,其后有N行数据,每行有N个0或1（数字之间没有空格,0表示可以通过,1表示不能通过）,用以描述迷宫地图.入口在左上角（1,1）处,出口在右下角（N,N）处.所有迷宫保证存在从入口到出口的可行路径. 【输出数据】输出数据仅一行,为从入口到出口的最短路径（有多条路径时输出任意一条即可）.路径格式参见样例. 【样例】 maze.in 4 0001 0100 0010 0110 maze.out (1,1)->(1,2)->(1,3)->(2,3)->(2,4)->(3,4)->(4,4) 怎么解,速度啊,谢谢

1个回答分类：综合 2014-11-14

问题解答：

我来补答

这题用广搜比较好. const wx:array[1..4] of integer=(1,0,-1,0); wy:array[1..4] of integer=(0,1,0,-1); var n,i,j:integer; a:array[1..20] of string[25]; qu:array[1..400,1..3] of integer; mark:array[1..20,1..20] of integer; list:array[1..400,1..2] of integer; procedure BFS(sx,sy,ex,ey:integer); //广搜 var x,y:integer; op,cl,m:integer; r:integer; begin fillchar(mark,sizeof(mark),0); cl:=0;op:=1; qu[1][1]:=sx;qu[1][2]:=sy;qu[1][3]:=0; //qu[][1]表示x坐标,qu[][2]表示y坐标,qu[][3]表示用于回朔的标记（即他的father） mark[sx][sy]:=1; //标记搜过,同时记录步数. while(cl0)and(y>0)and(x0)do begin list[m][1]:=qu[r][1]; list[m][2]:=qu[r][2]; inc(m); r:=qu[r][3]; end; dec(m); write('(',list[m][1],',',list[m][2],')'); for r:=m-1 downto 1 do write('->(',list[r][1],',',list[r][2],')'); writeln; end else writeln('No answer!'); end; begin readln(n); for i:=1 to n do readln(a[i]); BFS(1,1,n,n); end.

展开全文阅读