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);

    }
}