借助ACM1242题深入理解迷宫类最短路径搜索并记录路径长度的问题及解决方法；
这是初次接触优先队列，尤其是不知道该怎样去记忆在结构体重自定义大小比较的符号方向，很容易混淆符号向哪是从大到小排列，向哪是从小到大排列；
这非常向sort和qsort排序。
原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1242
1 #include<iostream> 2 #include<cstring> 3 #include<queue> 4 using namespace std; 5 const int N=1000; 6 char map[N][N]; 7 int vis[N][N]; 8 struct Node 9 { 10 int x,y,step; 11 friend bool operator<(Node v,Node u) 12 { 13 return v.step>u.step;//怎么记啊 14 } 15 }XX; 16 int n,m; 17 int direction[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; 18 bool Check(int x,int y) 19 { 20 if(x<0||y<0||x>=n||y>=m||map[x][y]=='#'||!vis[x][y]) 21 return false; 22 return true; 23 } 24 int dfs(Node S,Node E) 25 { 26 priority_queue<Node>Q; 27 S.step=0; 28 Q.push(S); 29 Node temp; 30 vis[S.x][S.y]=0; 31 while(!Q.empty()) 32 { 33 Node mid; 34 mid=Q.top(); 35 Q.pop(); 36 if(mid.x==E.x&&mid.y==E.y)return mid.step; 37 for(int i=0;i<4;i++) 38 { 39 Node next=mid; 40 next.x=mid.x+direction[i][0]; 41 next.y=mid.y+direction[i][1]; 42 if(Check(next.x,next.y)) 43 { 44 next.step++; 45 if(map[next.x][next.y]=='x') 46 next.step++; 47 if(vis[next.x][next.y]>next.step)//其实这步可以抛弃，只是增大下面优先队列的处理数据量 48 { 49 vis[next.x][next.y]=next.step;//其实也可以没有这一步 50 Q.push(next); 51 52 } 53 } 54 } 55 } 56 return -1;//返回它时说明无法到达目的地 57 } 58 int main() 59 { 60 while(cin>>n>>m) 61 { 62 memset(vis,1,sizeof(vis));//这里用的memset将vis赋特别大的值 ； 63 //memset一般用于赋值是-1和零，也用于char型符号赋值，但是当赋值为其他int型整数时， 64 //所得到的结果并不是你所写上的数，就像上面写的1，其实结果是很大的数，可以输出试验下； 65 Node s;//起点位置 66 Node e;//终点位置 67 for(int i=0;i<n;i++) 68 { 69 cin>>map[i]; 70 for(int j=0;j<m;j++) 71 if(map[i][j]=='a') 72 { 73 e.x=i;e.y=j; 74 } 75 else if(map[i][j]=='r') 76 { 77 s.x=i; 78 s.y=j; 79 } 80 else if(map[i][j]=='x')//是保存那个特出守卫的坐标的 81 { 82 XX.x=i;XX.y=j; 83 } 84 } 85 int time=dfs(s,e); 86 if(time==-1)cout<<"Poor ANGEL has to stay in the prison all his life."<<endl; 87 else cout<<time<<endl; 88 } 89 }
做这个题目话费了我好长好长时间，现在也不是太懂，不过还好啦，最起码理解这种方法了；算是长能力了。哈哈哈！