首页 > 代码库 > codevs 2059 逃出克隆岛
codevs 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
屠龙宝刀点击就送
#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>using namespace std;char tx[5000][5000];bool csm[5000][5000],vis[5000][5000];int cost,start_x,start_y,over_x,over_y,n,m,fx[5]={1,-1,0,0},fy[5]={0,0,-1,1};void print(int k){ printf("%d",k); exit(0);}void bfs(int sx,int sy){ int f[50000][4],l=0,r=0; f[++r][1]=sx; f[r][2]=sy; f[r][3]=0; do { int now_x=f[++l][1],now_y=f[l][2]; for(int j=0;j<4;++j) { int to_x=now_x+fx[j],to_y=now_y+fy[j]; if(to_x==over_x&&to_y==over_y) print(f[l][3]); if(to_x>=1&&to_x<=n&&to_y>=1&&to_y<=m&&tx[to_x][to_y]!=‘#‘&&vis[to_x][to_y]==0) { if(csm[to_x][to_y]==1) { f[++r][1]=to_x; f[r][2]=to_y; f[r][3]=f[l][3]; csm[to_x][to_y]=0; for(int i=1;i<=n;++i) { for(int k=1;k<=m;++k) { if(csm[i][k]==1) { csm[i][k]=0; f[++r][1]=i; f[r][2]=k; f[r][3]=f[l][3]; } } } } else { vis[to_x][to_y]=1; f[++r][1]=to_x; f[r][2]=to_y; if(tx[to_x][to_y]==‘*‘) f[r][3]=f[l][3]+cost; else f[r][3]=f[l][3]; } } } }while(l<=r);}int main(){ scanf("%d%d%d",&n,&m,&cost); for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { cin>>tx[i][j]; if(tx[i][j]==‘P‘) csm[i][j]=1; else if(tx[i][j]==‘Y‘) start_x=i,start_y=j; else if(tx[i][j]==‘C‘) over_x=i,over_y=j; } } bfs(start_x,start_y); printf("screw you!"); return 0;}
codevs 2059 逃出克隆岛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。