问题描述：
小鼠a与小鼠b身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这 m×n 个房间中有一些房间是封闭的，
不允许任何人进入。在迷宫中任何位置均可沿上，下，左，右4个方向进入未封闭的房间。小鼠a位于迷宫的(p，q)方格中，它必须找
出一条通向小鼠b所在的(r，s)方格的路。请帮助小鼠 a 找出所有通向小鼠b的最短道路。
编程任务：
对于给定的小鼠的迷宫，编程计算小鼠a通向小鼠b的所有最短道路。
数据输入(maze.in)：
由文件input.txt给出输入数据。第一行有3个正整数n，m，k，(n,m<=80)分别表示迷宫的行数，列数和封闭的房间数。接下
来的k 行中，每行2个正整数，表示被封闭的房间所在的行号和列号。最后的2行，每行也有2个正整数，分别表示小鼠 a 所处的方格
（p，q）和小鼠b所处的方格（r，s）。
结果输出(maze.out):
将计算出的小鼠a通向小鼠b的最短路长度和有多少条不同的最短路输出到文件maze.out。文件的第一行是最短路长度。文件的第
2行是不同的最短路数。如果小鼠a无法通向小鼠b则输出“No Solution!”。
|
输入文件示例 |
输出文件示例 |
|
Maze.in |
Maze.out |
|
8 8 3 3 3 4 5 6 6 2 1 7 7 |
11 96 |
思路：
首先由于小鼠可以上下左右移动，所以先排除动态规划（有后效型），然后想是否可以深搜，数据范围虽然不大，看似可以，
但实际上做到后面宽度将会非常的大，本人深搜超时3 个点（Orz），反正能广搜尽量广搜吧 - - 毕竟只要数组开够就好了。所以
锁定广搜~
其次，思考：对于这个决策点，记到该点的距离为dis ，要考虑它下一步到的上下左右四个方位，比如、对于它上面的位置，
如果由该决策点向上到达，则到上面那点的距离为dis+1，但此时就要考虑要不要将它加入广搜的数组，如果之前、到达上面那点
的距离比这次的小，那它必然不是最短路，就不能加入广搜数组。
所以在广搜的过程中，为了判定是否添加新的决策点，就要对到达每个点的最短路进行记录并且不断的更新，所以开一个min
数组记录到达每个点的最短距离，开始全部赋值为 maxlongint 。
PS ：对于要求的方案数 ，只要开一个num ，如果搜到了小鼠b的位置，有两种情况：
一、做到小鼠b 的位置时，距离小于原本到达小鼠b 的最小距离min[小鼠b 的横坐标，小鼠b 的纵坐标]，则先更新
min数组的值，因为之前的方案全没用了，不是最优的。
二、做到小鼠b 的位置时，距离等于原本到达小鼠b 的最小距离min[小鼠b 的横坐标，小鼠b 的纵坐标]，那么将 num
的值加一，因为最小距离方案数多一。
代码:
1 const g:array[1..4,1..2] of integer=((1,0),(0,1),(-1,0),(0,-1)); //向四个方向枚举的常数数组 2 var min,che:array[0..81,0..81] of longint; //min记录某点最短路径，che存障碍 3 gfs:array[0..4000000,1..3 ] of longint; //广搜数组 4 n,m,k,bx,by:longint; //bx，by为终点坐标 5 6 Procedure init; 7 var i,j,x,y:longint; 8 begin 9 readln(n,m,k); 10 for i:=1 to n do begin che[i,0]:=1; che[i,m+1]:=1; end; //建造边界 11 for i:=1 to m do begin che[0,i]:=1; che[n+1,i]:=1; end; //建造边界 12 for i:=1 to k do begin 13 readln(x,y); 14 che[x,y]:=1; //更新边界 15 end; 16 for i:=1 to n do 17 for j:=1 to m do min[i,j]:=maxlongint; //初始化最短路径 18 readln(gfs[1,1],gfs[1,2]); //从小鼠a 的位置开始广搜 19 readln(bx,by); 20 end; 21 22 Procedure main; 23 var i,j,top,tai,dx,dy:longint; //top为头指针，tai为尾指针， 24 //dx，dy为待决策点的坐标 25 begin 26 top:=0; 27 tai:=1; 28 repeat 29 inc(top); 30 for i:=1 to 4 do begin //从四个方向枚举待决策点 31 dx:=gfs[top,1]+g[i,1]; //更新待决策点横坐标 32 dy:=gfs[top,2]+g[i,2]; //更新待决策点纵坐标 33 if (che[dx,dy]=0)and(gfs[top,3]<min[bx,by]) then //如果该决策点无障碍并且该路径不比最优路径长 34 if gfs[top,3]+1<min[dx,dy] then begin //如果该路径比之前的最优路径短 35 if (dx=bx)and(dy=by) then num:=1; //如果是终点就维护方案数，清零之前方案 36 min[dx,dy]:=gfs[top,3]+1; //更新最短路径 37 inc(tai); //添加进广搜数组 38 gfs[tai,1]:=dx; 39 gfs[tai,2]:=dy; 40 gfs[tai,3]:=min[dx,dy]; 41 end else 42 if gfs[top,3]+1=min[dx,dy] then begin //否则就代表该路径和最优路径一样长 43 if (dx=bx)and(dy=by) then inc(num); //如果是终点就将方案数+1 44 inc(tai); //添加进广搜数组 45 gfs[tai,1]:=dx; 46 gfs[tai,2]:=dy; 47 gfs[tai,3]:=min[dx,dy]; 48 end; 49 end; 50 until top=tai; 51 end; 52 53 begin 54 assign(input,'maze.in'); assign(output,'maze.out'); 55 reset(input); rewrite(output); 56 init; main; 57 if num>0 then begin //如果有方案那么输出最短路径和方案 58 writeln(min[bx,by]); 59 writeln(num); 60 end else writeln('No Solution!'); //没方案输出无解 61 close(output); 62 end.
优化：
其实对于该数据范围，优化的效果不大，都很快。但如果数据范围一大，以下的一个优化可能就会有帮助：
很容易推断：如果对于一个无障碍方块，如果其上下左右有3 或四个障碍，那么这个方块可以视为是有障碍的，因
为对于一个格，进入该格后如果想出去，那么至少要走两个方向是没障碍的。并且地图的四周都可以视为是障碍，所以
可以对障碍先进行基本不影响复杂度的预处理。
END。