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潛規則

  下一篇： 大數與小數相乘算法