北京2018网络赛A题

题意：给你一个迷宫，迷宫有开始节点和结束节点，问你从开始走到结束的最小时间，其中，#代表这个点有毒气，身上必须带着氧气瓶才行，B代表每次进入这个点可以带一个氧气瓶，最多身上带五个，P代表进入这个点加速，不耗费时间

解题思路：就是bfs+优先队列，就是氧气瓶的地方麻烦点，我们只需要对于每个点，用一个多余的状态标记进入这个点身上氧气瓶的数量就可以了

代码：

#include<bits/stdc++.h>

using namespace std;

struct node

{

    int x,y,step,cnt;

    node(int _x=,int _y=,int _step=,int _cnt=):x(_x),y(_y),step(_step),cnt(_cnt){}

    friend bool operator<(node a,node b)

    {

        return a.step>b.step;

    }

}tmp,now;

char s[][];

int n,m,sx,sy;

int next1[][]={{-,},{,},{,},{,-}};

int visit[][][];

int bfs(int x,int y)

{

    priority_queue<node>que;

    que.push(node(x,y,,));

    while(!que.empty())

    {

        now=que.top();que.pop();

        if(s[now.x][now.y]=='T')

            return now.step;

        for(int i=;i<;i++)

        {

            tmp.x=now.x+next1[i][];tmp.y=now.y+next1[i][];

            if(tmp.x<||tmp.x>n||tmp.y<||tmp.y>m)

                continue;

            if(s[tmp.x][tmp.y]=='B')

            {

                tmp.cnt=min(,now.cnt+);tmp.step=now.step+;

                if(!visit[tmp.x][tmp.y][tmp.cnt])

                {

                    visit[tmp.x][tmp.y][tmp.cnt]=;

                    que.push(tmp);

                }

            }

            else if(s[tmp.x][tmp.y]=='P')

            {

                tmp.cnt=now.cnt;tmp.step=now.step;

                if(!visit[tmp.x][tmp.y][tmp.cnt])

                {

                    visit[tmp.x][tmp.y][tmp.cnt]=;

                    que.push(tmp);

                }

            }

            else if(s[tmp.x][tmp.y]=='#')

            {

                tmp.cnt=now.cnt-;tmp.step=now.step+;

                if(tmp.cnt<)

                    continue;

                if(!visit[tmp.x][tmp.y][tmp.cnt])

                {

                    visit[tmp.x][tmp.y][tmp.cnt]=;

                    que.push(tmp);

                }

            }

            else

            {

                tmp.cnt=now.cnt;tmp.step=now.step+;

                if(!visit[tmp.x][tmp.y][tmp.cnt])

                {

                    visit[tmp.x][tmp.y][tmp.cnt]=;

                    que.push(tmp);

                }

            }

        }

    }

    return -;

}

int main()

{

    while(cin>>n>>m&&n&&m)

    {

        memset(visit,,sizeof(visit));

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++)

        {

            cin>>s[i][j];if(s[i][j]=='S'){sx=i;sy=j;}

        }

        int ans=bfs(sx,sy);

        cout<<ans<<endl;

    }

}

巴特西

北京2018网络赛A题

最新文章

热门文章