674      阿里云  技术社区[云栖]

HDU 4308 BFS

题意：给出一个迷宫，王子的位置公主的位置，剩下的是，墙#、收费站*和传送点P。每过一次传送点需要付费cost。问你王子救到公主的最小花费。

这题用广搜就行，因为没有空白的点，从Y开始如果遇到p就把所有传送点送进队里就可以了。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
char map[5005][5005];
bool bj[5005][5005];
int r,c,cost;
int step[4][2]= {0,1,0,-1,1,0,-1,0};
struct point
{
    int x,y,cost;
    point() {}
    point(int _x,int _y,int _cost)
    {
        x=_x,y=_y,cost=_cost;
    }
};
int bfs(int x,int y)
{
    queue<point> myq;
    bj[x][y]=1;
    point now(x,y,0);
    myq.push(now);
    while(!myq.empty())
    {
        now=myq.front();
        myq.pop();
        for(int i=0; i<4; i++)
        {
            int nx=now.x+step[i][0],ny=now.y+step[i][1];
            if(nx<0||nx>=r||ny<0||ny>=c)
                continue;
            if(map[nx][ny]=='*'&&!bj[nx][ny])
            {
                bj[nx][ny]=1;
                point next(nx,ny,now.cost+cost);
                myq.push(next);
            }
            if(map[nx][ny]=='C')
                return now.cost;
            if(map[nx][ny]=='P'&&!bj[nx][ny])
                for(int j=0; j<r; j++)
                    for(int k=0; k<c; k++)
                        if(map[j][k]=='P')
                        {
                            point next(j,k,now.cost);
                            myq.push(next);
                            bj[j][k]=1;
                        }
        }
    }
    return -1;
}
int main()
{
    while(~scanf("%d%d%d",&r,&c,&cost))
    {
        int x=-1,y=-1;
        memset(bj,0,sizeof(bj));
        for(int i=0; i<r; i++)
        {
            scanf("%s",map[i]);
            if(x==-1&&y==-1)
                for(int j=0; j<c; j++)
                    if(map[i][j]=='Y')
                    {
                        x=i,y=j;
                        break;
                    }
        }
        int s=bfs(x,y);
        if(s==-1)
            puts("Damn teoy!");
        else
            printf("%d\n",s);
    }
    return 0;
}

最后更新：2017-04-03 18:52:03

  上一篇： App Store潜规则

  下一篇： 大数与小数相乘算法