牛客练习赛12 (3次 bfs)

71 阅读 0 评论 47 点赞

我是靠谱客的博主等待鸭子，最近开发中收集的这篇文章主要介绍牛客练习赛12 (3次 bfs)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

开始跑了一遍bfs发现不行，因为可能存在去拿钥匙在回来的
情况，无法用数组标记。
但是因为钥匙，起点，终点，门都各有一个，所以可以进行三次
dfs。
1.从起点到终点。
2.从起点去拿钥匙。在从钥匙的地点到终点。
这三次遍历都可以用mp数组标记，可以在规定时间内解决。
代码：

#include<bits/stdc++.h>
using namespace std;
char t[505][505];
bool mp[505][505];
int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct node
{
    int x,y,step;
};
queue<node> P;
int bfs1(int st,int en,int t1)
{
    while(!P.empty())P.pop();
    node r;r.x=st,r.y=en,r.step=0;
    P.push(r);
    memset(mp,0,sizeof(mp));
    mp[r.x][r.y]=1;
    while(!P.empty())
    {
        r=P.front();P.pop();
        if(t[r.x][r.y]=='E')
            return r.step;
        for(int i=0;i<4;i++)
        {
            int x=r.x+d[i][0],y=r.y+d[i][1];
            if((t[x][y]!='D'&&t[x][y]!='W')||(t[x][y]=='D'&&t1==1))
            {
                if(mp[x][y])
                    continue;
                node e;e.x=x;e.y=y;e.step=r.step+1;
                P.push(e);
                mp[e.x][e.y]=1;
            }
        }
    }
    return 1e9+7;
}
int bfs2(int st,int en)
{
    while(!P.empty())P.pop();
    memset(mp,0,sizeof(mp));
    node r;r.x=st;r.y=en;r.step=0;
    P.push(r);
    mp[r.x][r.y]=1;
    while(!P.empty())
    {
        r=P.front();P.pop();
        if(t[r.x][r.y]=='K')
            return r.step;
        for(int i=0;i<4;i++)
        {
            int x=r.x+d[i][0],y=r.y+d[i][1];
            if(t[x][y]!='W'&&t[x][y]!='D'&&!mp[x][y])
            {
                mp[x][y]=1;
                node e;e.x=x;e.y=y;e.step=r.step+1;
                P.push(e);
            }
        }
    }
    return 1e9+7;
}
int main()
{
    int n,m;
    memset(mp,0,sizeof(mp));
    scanf("%d%d",&n,&m);
    int i,j,x1,y1,x2,y2;
    for(i=0; i<n; i++)
        scanf("%s",&t[i]);
    for(i=0; i<n; i++)
        for(j=0; j<m; j++)
        {
            if(t[i][j]=='S')
                x1=i,y1=j;
            else if(t[i][j]=='K')
                x2=i,y2=j;
        }
    int ans=1e9;
    ans=min(bfs1(x1,y1,0),ans);
    int step=bfs2(x1,y1);
    if(step!=1e9+7)
    {
        step+=bfs1(x2,y2,1);
    }
    if(min(ans,step)<1e9)printf("%dn",min(ans,step));
    else printf("-1n");
    return 0;
}