逃出迷宫

逃出迷宫

时间限制: 1 Sec   内存限制: 128 MB

题目描述

现在有一个迷宫，'a'代表起点位置，'.'代表可以通行的路，'#'代表不能通过的墙，'x'代表迷宫的守卫，'r'代表终点位置， 现在要求你算出起点位置到终点位置的最短时间，其中通过'.'时，消耗1个单位时间，通过'x'消耗两个单位时间。

输入

多组测试数据，输入两个整数（X，Y）代表迷宫的长和宽，之后输入迷宫。

输出

如果可以到达终点，输出到达终点的最短时间。如果不能到达终点输出"Oh No!"。

样例输入

7 8 #.#####. #.a#..r. #..#x... ..#..#.# #...##.. .#...... ........

样例输出

13

简单广搜加上优先队列

#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<queue> using namespace std; char dp[1005][1005]; int vis[1005][1005]; int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};//所能到达的四个方向 int m,n,i,j; struct node { int x,y; int time; friend bool operator<(node a,node b)//优先队列 { return a.time>b.time; } }pre,now; void dfs() { priority_queue<node>Q; pre.time=0; Q.push(pre); vis[pre.x][pre.y]=1; while(!Q.empty()) { now=Q.top(); Q.pop(); if(dp[now.x][now.y]=='r') { cout<<now.time<<endl; return ; } for(i=0;i<4;i++) { pre.x=now.x+dir[i][0]; pre.y=now.y+dir[i][1]; pre.time=now.time+1; if(pre.x>=1&&pre.x<=m&&pre.y>=1&&pre.y<=n&&dp[pre.x][pre.y]!='#'&&vis[pre.x][pre.y]==0) { if(dp[pre.x][pre.y]=='x') pre.time+=1; vis[pre.x][pre.y]=1; Q.push(pre); } } } cout<<"Oh No!"<<endl; } int main() { while(cin>>m>>n) { getchar(); memset(vis,0,sizeof(vis)); for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { cin>>dp[i][j]; if(dp[i][j]=='a') { pre.x=i; pre.y=j; } } getchar(); } dfs(); } return 0; } 这道题和杭电上一道特别像 HDU 1242  Rescue  题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1242 代码： #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<queue> using namespace std; char map[205][205]; int n,m; int start1,start2; int to[4][2]= {{-1,0},{1,0},{0,-1},{0,1}}; //这个地方写的时候还出现了一些小问题，应该注意一下细节问题 struct node { int x,y; int time; friend bool operator<(node n1,node n2) { return n2.time<n1.time; } }; int bfs() { int i,j; priority_queue<node>Q; node p,next; p.x=start1; p.y=start2; p.time=0; Q.push(p); while(!Q.empty()) { p=Q.top(); Q.pop(); map[p.x][p.y]='#'; for(i=0; i<4; i++) { next.x=p.x+to[i][0]; next.y=p.y+to[i][1]; next.time=p.time+1; if(map[next.x][next.y]=='.') { Q.push(next); } if(map[next.x][next.y]=='a') return next.time; if(map[next.x][next.y]=='x') { next.time++; Q.push(next); } } } return -1; } int main() { int i,j; while(scanf("%d %d",&n,&m)!=EOF) { memset(map,'#',sizeof(map)); for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { cin>>map[i][j]; if(map[i][j]=='r') { start1=i; start2=j; } } } int num=bfs(); if(num!=-1) printf("%d\n",num); else printf("Poor ANGEL has to stay in the prison all his life.\n"); } return 0; } 那么什么是优先队列？又为什么会用到优先队列呢？ 下面就是对优先队列的使用示列 #include<iostream> #include<functional> #include<queue> using namespace std; struct node { friend bool operator< (node n1, node n2) { return n1.priority < n2.priority; } int priority; int value; }; int main() { const int len = 5; int i; int a[len] = {3,5,9,6,2}; //示例1 priority_queue<int> qi; for(i = 0; i < len; i++) qi.push(a[i]); for(i = 0; i < len; i++) { cout<<qi.top()<<" "; qi.pop(); } cout<<endl; //示例2 priority_queue<int, vector<int>, greater<int> >qi2; for(i = 0; i < len; i++) qi2.push(a[i]); for(i = 0; i < len; i++) { cout<<qi2.top()<<" "; qi2.pop(); } cout<<endl; //示例3 priority_queue<node> qn; node b[len]; b[0].priority = 6; b[0].value = 1; b[1].priority = 9; b[1].value = 5; b[2].priority = 2; b[2].value = 3; b[3].priority = 8; b[3].value = 2; b[4].priority = 1; b[4].value = 4; for(i = 0; i < len; i++) qn.push(b[i]); cout<<"优先级"<<'\t'<<"值"<<endl; for(i = 0; i < len; i++) { cout<<qn.top().priority<<'\t'<<qn.top().value<<endl; qn.pop(); } return 0; }

[