BFS问题。
题意是问 王子救公主 需要花费多少钱。每路过一个 * 就要支付 cost 那么多的钱。求最短。
多个P 传送点就 多个点进队即可。
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
int n,m,cost;
char g[5001][5001];
int xx[]={1,-1,0,0};
int yy[]={0,0,1,-1};
bool vis[5001][5001];
struct lx
{
int x,y;
int lv;
};
lx ss,ee;
lx p[2500001];
int pi;
int bfs()
{
memset(vis,0,sizeof(vis));
vis[ss.x][ss.y]=1;
lx tmp,now;
queue<lx>q;
q.push(ss);
int x,y,csx,csy;
while(!q.empty())
{
tmp=q.front();q.pop();
//printf("%d:%d %d\n",tmp.lv,tmp.x,tmp.y);
if(tmp.x==ee.x&&tmp.y==ee.y)return tmp.lv-1;
for(int k=0;k<4;k++)
{
x=tmp.x+xx[k];
y=tmp.y+yy[k];
if(x>=n||x<0||y>=m||y<0||g[x][y]=='#'||vis[x][y])
continue;
vis[x][y]=1;
if(g[x][y]=='P')
{
for(int i=0;i<pi;i++)
{
if(x==p[i].x&&y==p[i].y)continue;
now.x=p[i].x;
now.y=p[i].y;
now.lv=tmp.lv;
q.push(now);
}
continue;
}
now.x=x,now.y=y;
now.lv=tmp.lv+1;
q.push(now);
}
}
return -1;
}
int main()
{
while(scanf("%d%d%d",&n,&m,&cost)!=EOF)
{
pi=0;
for(int i=0;i<n;i++)
{
scanf("%s",g[i]);
for(int j=0;j<m;j++)
{
if(g[i][j]=='Y')
ss.x=i,ss.y=j,ss.lv=0;
else if(g[i][j]=='C')
ee.x=i,ee.y=j;
else if(g[i][j]=='P')
{
p[pi].x=i,p[pi].y=j;
pi++;
}
}
}
int tmp=bfs();
if(tmp==-1)puts("Damn teoy!");
else
printf("%d\n",tmp*cost);
}
}
HDU 4308 Saving Princess claire_,布布扣,bubuko.com
HDU 4308 Saving Princess claire_
原文：http://blog.csdn.net/dongshimou/article/details/37765287