纯BFS+优先队列扩展。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <queue>
using namespace std;
bool vis[5100];
char str[5100];
struct point{
int x,y;
int cost;
bool operator < (const point &a)const{
return cost>a.cost;
}
}st,en,passort[550],tmp,pushed;
int pp;
priority_queue<point>que;
int dir[4][2]={
{0,1},{0,-1},{1,0},{-1,0}
};
int work(int r,int c,int cost){
memset(vis,false,sizeof(vis));
int x,y;
st.cost=0;
que.push(st);
vis[st.x*c+st.y]=true;
while(!que.empty()){
tmp=que.top();
que.pop();
for(int i=0;i<4;i++){
x=tmp.x+dir[i][0],y=tmp.y+dir[i][1];
if(x>=0&&x<r&&y>=0&&y<c){
if(str[x*c+y]!='#'&&!vis[x*c+y]){
if(str[x*c+y]=='*'){
pushed.x=x;
pushed.y=y;
pushed.cost=tmp.cost+cost;
que.push(pushed);
vis[x*c+y]=true;
}
else if(str[x*c+y]=='P'){
for(int ps=0;ps<pp;ps++){
pushed.x=passort[ps].x;
pushed.y=passort[ps].y;
pushed.cost=tmp.cost;
que.push(pushed);
vis[x*c+y]=true;
}
}
else if(str[x*c+y]=='C')
return tmp.cost;
}
}
}
}
return -1;
}
int main(){
int r,c,cost;
while(scanf("%d%d%d",&r,&c,&cost)!=EOF){
getchar();
int beg=0;
pp=0;
for(int i=0;i<r;i++){
gets(str+beg);
for(int k=beg;k<beg+c;k++)
if(str[k]=='Y'){
st.x=i;
st.y=k-beg;
}
else if(str[k]=='C'){
en.x=i;
en.y=k-beg;
}
else if(str[k]=='P'){
passort[pp].x=i;
passort[pp].y=k-beg;
pp++;
}
beg+=c;
}
int ans=work(r,c,cost);
if(ans==-1) printf("Damn teoy!
");
else
printf("%d
",ans);
while(!que.empty())
que.pop();
}
return 0;
}