题目描述 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<queue>
#include<cstdio>
#include<cstring>
#include<cstdlib> using namespace std; struct node {
int x,y,dis;
};
struct node cur_1,cur_2,cur_3; const int dx[]={,-,,,};
const int dy[]={,,,,-}; int n,m,p,num_P=,px[],py[],ex,ey,sx,sy;
int pd[][]; char map[][]; queue<struct node>que; void bfs()
{
memset(pd,/,sizeof(pd));
cur_1.x=sx,cur_1.y=sy,cur_1.dis=;
que.push(cur_1);
pd[sx][sy]=;
while(!que.empty())
{
cur_1=que.front();
que.pop();
for(int i=;i<=;i++)
{
if(cur_1.x+dx[i]>&&cur_1.x+dx[i]<=n&&cur_1.y+dy[i]>&&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=;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=;i<=n;i++)
{
scanf("%s",map[i]+);
for(int j=;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]>) printf("screw you!\n");
else printf("%d\n",pd[ex][ey]);
return ;
}