2695 - 掉线城与虚弱勇士
去年的12月1日的ACM校赛后，小明玩的《轩辕剑天之痕》已经被他通关了。他顺便也学习了游戏编程中很重要的搜索算法，毕竟很多公司笔试和面试都会考察。
现在大二的小明很喜欢玩一种网络游戏——《掉线城与虚弱勇士》
<span style="font-size:10.5pt;font-family:'宋体';">在这个游戏的迷宫中，你必须争分夺秒的从迷宫的入口走到出口，否则就会遇到掉线这种超级大<span>BOSS</span><span>把你一刀秒杀。在这种掉线的环境中，每走一步路需要花费一分钟的时间。</span></span><span style="font-size:10.5pt;font-family:'宋体';"></span>
<span style="font-size:10.5pt;font-family:'宋体';">需要注意的是，迷宫中会有一些守卫，这些守卫很弱小，但是他们会拖延你一分钟的时间，使你更加接近掉线。</span><span style="font-size:10.5pt;font-family:'宋体';"></span>
<span style="font-size:10.5pt;font-family:'宋体';">你要做的是在最短的时间中冲出这个迷宫，计算出这个最短的时间。</span><span style="font-size:10.5pt;font-family:'宋体';"></span>
<span style="font-size:10.5pt;font-family:'宋体';">PS<span>：守卫不一定要打，想办法在最短时间内冲出迷宫才是第一任务。</span></span><span style="font-size:10.5pt;font-family:'宋体';"></span>
Input
第一行是一个整数T，表示测试数据的组数（1<T<5)
对每一组测试样例，第一行为N，M，表示一个N*M的矩阵，即迷宫本身。(N,M<=100)
对迷宫来说，字符"." 代表路, "a" 小明的角色起始的位置, "r" 代表出口的位置， "x"代表守卫的位置。
Output
对每组测试数据，输出一行数据，表示最短花费的时间。
如果小明根本走不出去迷宫，请输出“Poor XIAOMING has to stay in the prison all his life.”
Examples
Input
1 7 8 #.#####. #.a#..r. #..#x... ..#..#.# #...##.. .#...... ........
Output
13
Solution C++
#include<iostream> #include<string.h> #include<stdio.h> #include<ctype.h> #include<algorithm> #include<stack> #include<queue> #include<set> #include<math.h> #include<vector> #include<deque> #include<fstream> #include<list> #define maxn 210 using namespace std; struct N { int x; int y; int step; bool operator<(const N &a)const//两个const不可少 { return a.step<step; } } p; int dis[4][2]= {0,1,0,-1,1,0,-1,0}; int m,n; int ans; char map[maxn][maxn]; bool vis[maxn][maxn]; int sx,sy,ex,ey; bool check(int x,int y) { if(x>=0&&y>=0&&x<m&&y<n&&vis[x][y]==0&&map[x][y]!='#') return true; else return false; } void bfs() { priority_queue<N> pq;//若优先队列是全局变量、则每次都要清空队列 N now,next; now.x=sx; now.y=sy; now.step=0; vis[now.x][now.y]=1; pq.push(now); while(!pq.empty()) { now=pq.top(); pq.pop(); if(now.x==ex&&now.y==ey) { ans=now.step; return ; } for(int i=0; i<4; i++) { next=now; next.x+=dis[i][0]; next.y+=dis[i][1]; if(check(next.x,next.y)) { next.step=now.step+1; vis[next.x][next.y]=1; if(map[next.x][next.y]=='x') next.step+=1; pq.push(next); } } } ans=-1; return ; } int main() { //ofstream cout; //ifstream cin; //cin.open("e.in"); //cout.open("e.out"); int testcase; cin>>testcase; while(testcase--) { cin>>m>>n; ans=0; memset(vis,0,sizeof(vis)); memset(map,0,sizeof(map)); for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { cin>>map[i][j]; if(map[i][j]=='a') { sx=i; sy=j; } if(map[i][j]=='r') { ex=i; ey=j; } } } bfs(); if(ans!=-1) cout<<ans<<endl; else cout<<"Poor XIAOMING has to stay in the prison all his life."<<endl; } return 0; }