首页 > 代码库 > Codevs 2059 逃出克隆岛

Codevs 2059 逃出克隆岛

2024-08-31 22:48:00   207人阅读

　　　　　　　　　　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

 

#include<cstdio>#include<cstring>#include<iostream>using namespace std;int n,m,cost,sx,sy,ex,ey,tot=0;int u[5]={0,0,1,0,-1};int v[5]={0,1,0,-1,0};int x[10010],y[10010],dis[10010];//dis数组记录花费 char map[1010][1010];bool used[1010][1010],chuan[1010][1010];//记录传送门坐标 bool flag;void bfs(int x1,int y1){    int tt=0,ww=1;used[x1][y1]=1;x[1]=x1;y[1]=y1;dis[1]=0;    while(tt<ww)    {        tt++;        for(int i=1;i<=4;i++)//四个方向         {            int xx=x[tt]+u[i];            int yy=y[tt]+v[i];            if(xx==ex&&yy==ey)            {                flag=1;                printf("%d",dis[tt]);//输出花费                 return ;            }            if(xx>0&&xx<=n&&yy>0&&yy<=m&&map[xx][yy]!=‘#‘&&!used[xx][yy])            {                if(chuan[xx][yy])                {                    chuan[xx][yy]=0;                    for(int i=1;i<=n;i++)                        for(int j=1;j<=m;j++)                            if(chuan[i][j])                            {                                ww++;                                x[ww]=i;y[ww]=j;chuan[i][j]=0;                                dis[ww]=dis[tt];//更新dis数组                             }                }                ww++;x[ww]=xx;y[ww]=yy;used[xx][yy]=1;                if(map[xx][yy]==‘*‘) dis[ww]=dis[tt]+cost;                //如果走的是*让dis数组加上花费                 else dis[ww]=dis[tt];//否则不加             }        }    }}int main(){    scanf("%d%d%d",&n,&m,&cost);    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)        {            cin>>map[i][j];            if(map[i][j]==‘Y‘) sx=i,sy=j;            else if(map[i][j]==‘C‘) ex=i,ey=j;            else if(map[i][j]==‘P‘) chuan[i][j]=1;        }    bfs(sx,sy);    if(!flag) printf("screw you!\n");    return 0;}

　　思路：走到传送门的时候将别的传送门边上的点一并入队，广搜..

Codevs 2059 逃出克隆岛


联系
我们