Description
如下图12×12方格图，找出一条自入口（2，9）到出口（11，8）的最短路径。
Output
Sample Input
12 //迷宫大小
2 9 11 8 //起点和终点 1 1 1 1 1 1 1 1 1 1 1 1 //邻接矩阵，0表示通，1表示不通 1 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Sample Output(2,9)->(3,9)->(3,8)->(3,7)->(4,7)->(5,7)->(5,6)->(5,5)->(5,4)->(6,4)->(7,4)->(7,3)->(7,2)->(8,2)->(9,2)->(9,3)->(9,4)->(9,5)->(9,6)->(8,6)->(8,7)->(8,8)->(9,8)->(9,9)->(10,9)->(11,9)->(11,8)
27这题我们用的算法是广度优先搜素。
我们先定义head和tail两个指针，每一次判断这个点可不可以走，如果可以就将该定点记录下来。
代码如下：
const dx:array[1..4]of longint=(1,-1,0,0); dy:array[1..4]of longint=(0,0,1,-1);var a:array[1..100,1..100]of longint; n,b1,b2,e1,e2,l,tail:longint; state:array[1..100,1..2]of longint; father:array[1..100]of longint;procedure init;var i,j:longint;begin readln(n); readln(b1,b2,e1,e2); for i:=1 to n do begin for j:=1 to n do read(a[i,j]); readln; end;end;function check(x,y:longint):boolean;begin if a[x,y]=0 then check:=true else check:=false;end;procedure print(x:longint);begin if x=0 then exit; inc(l); print(father[x]); if x<>tail then write('(',state[x,1],',',state[x,2],')->') else writeln('(',state[x,1],',',state[x,2],')');end;procedure bfs;var head,i:longint;begin head:=0; tail:=1; state[1,1]:=b1; state[1,2]:=b2; father[1]:=0; repeat inc(head); for i:=1 to 4 do if check(state[head,1]+dx[i],state[head,2]+dy[i])=true then begin inc(tail); father[tail]:=head; state[tail,1]:=state[head,1]+dx[i]; state[tail,2]:=state[head,2]+dy[i]; a[state[tail,1],state[tail,2]]:=1; if (state[tail,1]=e1)and(state[tail,2]=e2) then begin print(tail); tail:=0; end; end; until head>=tail;end;begin init; bfs; writeln(l);end.