游客 注册 | 登录
中文 | En

2695 - 掉线城与虚弱勇士

通过次数

0

提交次数

0

时间限制 : 5 秒 内存限制 : 128 MB

去年的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> 


&nbsp;

题目输入

第一行是一个整数T，表示测试数据的组数（1<T<5)

对每一组测试样例，第一行为N，M，表示一个N*M的矩阵，即迷宫本身。(N,M<=100)

对迷宫来说，字符"." 代表路, "a" 小明的角色起始的位置,  "r" 代表出口的位置， "x"代表守卫的位置。

题目输出

对每组测试数据，输出一行数据，表示最短花费的时间。

如果小明根本走不出去迷宫，请输出“Poor XIAOMING has to stay in the prison all his life.”

输入/输出样例

输入格式

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

输出格式

13

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;
}
请先登陆