Question

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)
（在线等答案）

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励10（财富值+成长值）+提问者悬赏20（财富值+成长值）

Answer 1

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.