题解 P1374 【进攻幽暗城】

· · 题解

My Blog

首先,你要知道什么是 \text{bfs}

若不知道,可以看一下这道题:P1443(很好的bfs入门) 以及我的题解

个人认为,这道题应在 \text{提高+/省选-} 这个样子,细节有点多

由于 \text{Answer} \leq 100 所以我们考虑预处理出魔王和萨尔的位置,进行 \text{bfs}

详细看注释吧

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10050
class Queue{//手写队列,防止被卡,养成好习惯,从你我做起
    private:int a[N+50],l,r;
    public:int siz;
        inline void clear(){l=r=siz=0;}
        inline void push(const int x){a[r++]=x;siz++;if(r>N) r=0;}
        inline void pop(){l++;siz--;if(l>N) l=0;}//循环队列
        inline int front(){return a[l];}
}qx,qy,qt,qstep;
const int xx[5]={0,-1,1,0,0},yy[5]={0,0,0,-1,1};
/*
分别对应:不动;上;下;左;右移动时x轴和y轴的变化
*/
#include<cmath>
/*
不能用"y1"这个变量名!!
*/
int n,m,s,Map[150][150],Lensaer,Lenmw;
int sax[150],say[150],mx[150],my[150];
char Strsaer[150],Strmw[150],Str[150];
double d;
int main(){
    scanf("%d%d%d%lf",&n,&m,&s,&d);
    for(int i=1;i<=n;++i){
        scanf("%s",Str+1);
        for(int j=1;j<=m;++j)
            Map[i][j]=Str[j]-48;
    }
    scanf("%d%d%d%d",&sax[0],&say[0],&mx[0],&my[0]);
    scanf("%s",Strsaer+1);
    scanf("%s",Strmw+1);
    Lensaer=strlen(Strsaer+1);
    Lenmw=strlen(Strmw+1);
    for(int i=1;i<=100;++i){
        sax[i]=sax[i-1]+xx[Strsaer[(i-1)%Lensaer+1]-48];
        say[i]=say[i-1]+yy[Strsaer[(i-1)%Lensaer+1]-48];//看不懂可以手动模拟一下
        if(Map[sax[i]][say[i]] || sax[i]<1 || sax[i]>n || say[i]<1 || say[i]>m)
            sax[i]=sax[i-1],say[i]=say[i-1];
    }
    for(int i=1;i<=100;++i){
        mx[i]=mx[i-1]+xx[Strmw[(i-1)%Lenmw+1]-48];
        my[i]=my[i-1]+yy[Strmw[(i-1)%Lenmw+1]-48];
        if(Map[mx[i]][my[i]] || mx[i]<1 || mx[i]>n || my[i]<1 || my[i]>m)
            mx[i]=mx[i-1],my[i]=my[i-1];
    }
    //预处理出位置
    qx.push(sax[0]);
    qy.push(say[0]);
    qt.push(0);
    qstep.push(0);
    //初始状态
    while(qx.siz){
        int x=qx.front();
        int y=qy.front();
        int t=qt.front();
        int step=qstep.front();
        qx.pop();
        qy.pop();
        qt.pop();
        qstep.pop();
            //取出队首并弹出
        if(sqrt(1.0*(x-sax[step])*(x-sax[step])+1.0*(y-say[step])*(y-say[step]))>d) ++t;
            //若距离大于d则离开时间+1
        else t=0;
        if(t>s) continue;
        if(x==mx[step] && y==my[step]){//找到最优解
            printf("%d\n",step);
            break;
        }
        if(x==mx[step+1] && y==my[step+1]){//若不动可以在下一步遇到魔王
            qx.push(x);
            qy.push(y);
            qt.push(t);
            qstep.push(step+1);
            continue;
        }
        for(int i=1;i<=4;++i){//枚举上下左右
            if(Map[x+xx[i]][y+yy[i]] || x+xx[i]<1 || x+xx[i]>n || y+yy[i]<1 || y+yy[i]>m) continue;
                //注意细节
            qx.push(x+xx[i]);
            qy.push(y+yy[i]);
            qt.push(t);
            qstep.push(step+1);//存储下一个状态,压入队尾
        }
    }
    return 0;
}