这问题是在博客上看到的，为此学习一下，然后在他的基础上，改动完毕迷宫洪水流算法的实现

题目是

Problem DescriptionAngel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)InputFirst line contains two integers stand for N and M.Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend. Process to the end of the file.OutputFor each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life." Sample Input7 8#.#####.#.a#..r.#..#x.....#..#.##...##...#..............Sample Output13

先给出博主的算法

源码

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef struct p{    int x,y,t;    bool operator < (const p &a) const    {        return t>a.t;    }}Point;char map[20][20];Point start;int n,m;int dir[][2]={
     {
     1,0},{-1,0},{
     0,1},{
     0,-1}};void show(){    cout<
           
             que; Point cur,next; int i; map[start.x][start.y]='#'; que.push(start); show(); while(!que.empty()) { cur=que.top(); que.pop(); for(i=0;i<4;++i) { next.x=cur.x+dir[i][0]; next.y=cur.y+dir[i][1]; next.t=cur.t+1; if( next.x<0 || next.x>=n || next.y<0 || next.y>=m) continue; if(map[next.x][next.y] == '#') continue; if(map[next.x][next.y]=='r') return next.t; if(map[next.x][next.y]=='.') { map[next.x][next.y]='#'; que.push(next); } else if(map[next.x][next.y]=='x') { map[next.x][next.y]='#'; next.t++; que.push(next); } show(); } } return -1;}int main(){ freopen("test.txt","r",stdin); int i,ans; char* p; cin>>n>>m; for (i=0;i
           
          
         
        
       
      

本质就是求a到r的最短路径。差别于一般的最短路径，这里通过x是要时间加倍的。

这里研究一下，为什么使用这样的优先队列能够找到最短路径

• 怎样实现这个搜索过程

回溯法得到的不一定是最小路径。仅仅实用回溯找到所有路径比較才还能得到最短路径。

这里面会涉及到stl的priority_queue这个类，这是一个涉及权重的队列，

首先将这个类研究一下，以后涉及权重的就能够使用这个类了

这里研究一下，为什么使用这样的优先队列能够找到最短路径

这个算法的基本思路就是 从cur到next去两点之间找权重（时间）最短的路径

利用priorit_queue来查找

在每次走过一个点都将此点标志为走过；

第一次

从開始点出发，进入while循环

此时cur为起始点，队列为空，将起始点标记为“#”

開始在cur上下左右寻找可走路径，向下找到后，压入队列，并标志“#”

四次寻找结束。

将找到的两个路径，入队列。

第二次

在队列中找到t最小的点。作为cur点

此时两个一样，看看

top出来的是左边那个点（2。2）。top出来之后将这个点从队列中pop掉，表示这个点已经走过

再次以cur为中心，寻找周围的有效点并压队列。此时上次没有选中的点（1，1）还在队列里面。由于假设此路不通还要返回这个点

第三次

此时在利用优先级推断，选择下一个要走的点

此时在队列里面，优先级最高的反而编程上一次没有选择的，就是点（1。1），

此时将（1，1）点top出来，而且pop掉。cur变为点（1。1）

这时有点像，从出发点向四个方向发散出去，每一个方向都要搜索。

搜索cur周围点之后

标记地图为

进入下一步，优先判决

第四次

此时队列里面的点处于同一优先级。

这里会有一种情况，由于处于边上的点（0，1），即使选择它，由于没有以下的点，所以pop之后就不存在了，

就会继续往下搜索，

此时系统选择的是点（2，1）为cur，再将cur四个方向有效点压队列。

图示为

进入下一次判决

第五次

此时将之前优先级低的top出来，并pop掉。

选择的是点（0，1），由于cur点周围没有有效路径，所以，没有新的有效点压入，所以这个方向就不再搜索了

。

。

。。

。

重复以往。直到先遇到X点

在cur点为（3，4）是搜索到上面有x点，此时权重须要多加一个一

继续 直到cur点为（2，6）时。检測到r的位置，此时。返回权重就是最短的时间路程

对于总体的各个思路，这好像是一个广度搜索，和回溯法的深度优先不太一样。基于此

能否够用树来表示搜索过程

先看一个最简单的模型

标出路径

优先队列的搜索树图

括号中为（X,Y.priority）

所以其基本思路就是从出发点開始向外扩展。利用优先队列。存储扩展时的路长，直到找到目标点。

这个能够计算出路径的长度，对于路径的走法。

这样的方法 非常像洪水流算法

然后从b回溯

再看一个样例

两条路径都是能够找到最短的

这样的洪水的思想也就能够用上面优先队列来实现

所以 假设将每次压入队列的点的权重保存到地图中，这样就能够完毕洪水流的操作了

改动函数为

int bfs(){ priority_queue 
      
        que; Point cur,next; int i; char db; //map[start.x][start.y]='#'; que.push(start); show(); while(!que.empty()) {  cur=que.top();  que.pop();  for(i=0;i<4;++i)  {   next.x=cur.x+dir[i][0];   next.y=cur.y+dir[i][1];   next.t=cur.t+1;   if( next.x<0 || next.x>=n || next.y<0 || next.y>=m)    continue;   if(map[next.x][next.y] == '#')    continue;   if(map[next.x][next.y]=='r')    return next.t;   if(map[next.x][next.y]=='.')   {    db=next.t>9?
      

(next.t-10+'a'):(next.t+'0'); map[next.x][next.y]=db; que.push(next); } show(); } } return -1; }

执行结果为

（10以后用abc表示）

这样就能够输出其路径了

• 怎样将路径输出
  另一个问题要解决 。就是怎样从b返回到a。
  能够採用和如队列之前一样的算法，因cur和next分别查找上下左右，是否符合。然后交替cur和next
  代码为

void print_path(void){ Point cur,next; int i; cur=end; while (!((cur.x==start.x)&&(cur.y==start.y))) {  for(i=0;i<4;++i)  {   next.x=cur.x+dir[i][0];   next.y=cur.y+dir[i][1];   if(map[next.x][next.y]==map[cur.x][cur.y]-1)    break;  }  cout<<"x= "<
      
       <<"y= "<
       
        <
       
      

ps为了方便优先级都用int转char，可能打出来非常难看

执行结果为

找到了回来的路径

所有測试代码为

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;/*int main(){ priority_queue 
           
            
             ,greater
             
              > pq; pq.push(6); pq.push(1); pq.push(3); pq.push(2); pq.push(9); while (!pq.empty()) { cout<
              
               <<" "; pq.pop(); } cout<
               
                a.t; }}Point;char map[20][20];Point start;Point end;int n,m;int dir[][2]={ { 1,0},{-1,0},{ 0,1},{ 0,-1}};void show(){ cout<
                
                  que; Point cur,next; int i; char db; map[start.x][start.y]=0; que.push(start); show(); while(!que.empty()) { cur=que.top(); que.pop(); for(i=0;i<4;++i) { next.x=cur.x+dir[i][0]; next.y=cur.y+dir[i][1]; next.t=cur.t+1; if( next.x<0 || next.x>=n || next.y<0 || next.y>=m) continue; if(map[next.x][next.y] == '#') continue; if(map[next.x][next.y]=='e') { map[next.x][next.y]=next.t; end=next; return next.t; } if(map[next.x][next.y]=='.') { //db=next.t>9?
                
               
              
             
            
           
          
         
        
       
      

(next.t-10+'a'):(next.t+'0'); map[next.x][next.y]=next.t; que.push(next); } show(); } } return -1; } void print_path(void) { Point cur,next; int i; cur=end; while (!((cur.x==start.x)&&(cur.y==start.y))) { for(i=0;i<4;++i) { next.x=cur.x+dir[i][0]; next.y=cur.y+dir[i][1]; if(map[next.x][next.y]==map[cur.x][cur.y]-1) break; } cout<<"x= "<<next.x<<"y= "<<next.y<<endl; cur=next; } } int main() { freopen("test.txt","r",stdin); int i,ans; char* p; cin>>n>>m; for (i=0;i<n;++i) { scanf("%s",map[i]); if(p=strchr(map[i],'s')) { start.x=i; start.y=p-map[i]; start.t=0; } //printf("%s\n",map[i]); } ans=bfs(); cout<<"ans "<<ans<<endl; show(); print_path(); return 0; } test.txt为 7 8 #.#####. #.s#..e. #..#.... ..#..#.# #...##.. .#...... ........