2059 逃出克隆岛

 

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

 

 

 

题目描述 

Description

oi小组的yh酷爱玩魔兽rpg，每天都会在u9搜索最新的rpg地图。

今天，他找到一张名为《逃出克隆岛》的地图，在这张地图中，有一个n行m列的矩阵，矩阵由’Y’，’C’，’#’，’*’，’P’,5种元素组成。’Y’表示yh的出生位置，C表示克隆岛的出口，’#’表示该处不可通过，’*’表示通过该处需要消耗金币cost,’P’表示传送阵，任意两个传送阵之间可以免费互相传送。由于这仅仅是第一关，yh不想浪费太多的体力，聪明的你能帮他算出从’Y’出发到’C’最少需要消耗多少金币吗？当然，如果yh永远无法到达’C’,请输出” screw you!”以表到yh的不满。

输入描述 

Input Description

第一行两个整数，n,m,表示矩阵有n行m列

接下来为n行m列的矩阵，由’Y’,’C’,’#’,’*’,’P’,组成，含义如题目描述。

输出描述 

Output Description

输出1行，表示yh需要花费的最小体力（如果无法到达输出”screw you!”）。

样例输入 

Sample Input

【样例输入1】

1 3 3

Y*C

【样例输入2】

1 3 2

Y#C

【样例输入3】

1 5 2

YP#PC

样例输出 

Sample Output

【样例输出1】

3

【样例输出2】

screw you!

【样例输出3】

0

数据范围及提示 

Data Size & Hint

【数据范围】

对于100%的数据，n*m≤5000，传送阵’P’的数量≤500

 

 

思路：

　　暴力bfs强行ac

 

来，上代码：

#include
          
           #include
           
            #include
            
             #include
             
              using namespace std;struct node {    int x,y,dis;};struct node cur_1,cur_2,cur_3;const int dx[5]={
        0,-1,0,1,0};const int dy[5]={
        0,0,1,0,-1};int n,m,p,num_P=0,px[510],py[510],ex,ey,sx,sy;int pd[5010][5010];char map[1010][1010];queue
              
               que;void bfs(){    memset(pd,127/3,sizeof(pd));    cur_1.x=sx,cur_1.y=sy,cur_1.dis=0;    que.push(cur_1);    pd[sx][sy]=0;    while(!que.empty())    {        cur_1=que.front();        que.pop();        for(int i=1;i<=4;i++)        {            if(cur_1.x+dx[i]>0&&cur_1.x+dx[i]<=n&&cur_1.y+dy[i]>0&&cur_1.y+dy[i]<=m)            {                if(map[cur_1.x+dx[i]][cur_1.y+dy[i]]=='#') continue;                if(pd[cur_1.x+dx[i]][cur_1.y+dy[i]]<=cur_1.dis) continue;                pd[cur_1.x+dx[i]][cur_1.y+dy[i]]=cur_1.dis;                cur_2.x=cur_1.x+dx[i],cur_2.y=cur_1.y+dy[i],cur_2.dis=cur_1.dis;                if(map[cur_1.x+dx[i]][cur_1.y+dy[i]]=='*')                {                    cur_2.dis+=p;                    que.push(cur_2);                }                if(map[cur_2.x][cur_2.y]=='P')                {                    que.push(cur_2);                    for(int j=1;j<=num_P;j++)                    {                        if(pd[px[j]][py[j]]<=cur_2.dis) continue;                        pd[px[j]][py[j]]=cur_2.dis;                        cur_3.x=px[j],cur_3.y=py[j],cur_3.dis=cur_2.dis;                        que.push(cur_3);                    }                }                if(map[cur_2.x][cur_2.y]=='Y'||map[cur_2.x][cur_2.y]=='C') que.push(cur_2);            }        }    }}int main(){    scanf("%d%d%d",&n,&m,&p);    for(int i=1;i<=n;i++)    {        scanf("%s",map[i]+1);        for(int j=1;j<=m;j++)        {            if(map[i][j]=='P') px[++num_P]=i,py[num_P]=j;            if(map[i][j]=='C') ex=i,ey=j;            if(map[i][j]=='Y') sx=i,sy=j;        }    }    bfs();    if(pd[ex][ey]>100000) printf("screw you!\n");    else printf("%d\n",pd[ex][ey]);    return 0;}