题解 P4872 【OIer们的东方梦】

· · 题解

调了一天，终于过了~写篇题解纪念一下~

感觉我的代码比起其他人的可读性要高许多。。。

感谢disangan233提供神仙题面，感谢上海爱丽丝幻乐团提供信仰，能有信心磕这道题的估计大部分是車万党吧。。。

废话不多说：我们先来分析一下题：

这题细节很多，过样例却WA掉的可以看看代码中的具体注释。

我采用了优先队列BFS的方法，于是每个点有几个属性：坐标，dis值，是否抢剑，是否偷花。

我们再定义一个NB值，什么都没有时NB=0，有花时NB=1，有剑时NB=2.

分析每个字符：

0,1,2,3都好说，就是NB值不一样时距离不同。

4:偷花不需要时间，可以直接修改属性。

5:注意可以不要剑，所以要考虑要和不要两种情况。

M:关于麻薯。。。藏起来就好，别让幽幽子看到。

X:最麻烦的一个，可以满地图乱窜，每次都枚举复杂度是不行的，但是你发现每个NB值状态下最多只用传送一次就行，没必要传来传去，直接传到最后一次的位置不就行了。除非你专程去偷花或抢剑，那样会使你的NB值增加，所以每个NB值下都可以考虑传送，传送过就可以忽略X了。

那就看代码吧：具体操作都在代码里了~

自我感觉可读性良好。。。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define QWQ cout<<"QwQ"<<endl;
#define ll long long 
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
const int N=101010;
const int qwq=303030;
const int inf=0x3f3f3f3f;
int n,m;
int g,h,s,t;                         //起点和终点的坐标 
char z[1234][1234];
int dis[1234][1234][3];              //每个NB值状态下的dis值 
bool bayunzi[4];                     //在这个NB值状态下是否用过间隙 
int ff[] = {1,0,0,-1};
int gg[] = {0,1,-1,0};               //4个方向 
struct E{
    int d;
    int i,j; 
    bool lou,hua;                    //lou：是否有楼观剑，hua：是否抢过花 
};
priority_queue <E> q;                //优先队列，对d优先 
inline bool operator < (E aa,E bb) { return aa.d > bb.d; }

inline int getNB(E v) {             //获得NB值 
    if(v.lou) return 2;
    if(v.hua) return 1;
    return 0;
}

inline void check(E v) {            //更新dis值，并压入队列 
    int NB = getNB(v);
    if(v.d >= dis[v.i][v.j][NB]) return ;
    dis[v.i][v.j][NB] = v.d;     q.push(v);
}

void jian_xi(E u) {                     //从间隙往别的间隙走 
    int NB = getNB(u);
    if(bayunzi[NB]) return ; bayunzi[NB] = 1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) {
        if(z[i][j]!='X') continue;
        E v = (E){u.d+1, i, j, u.lou, u.hua};
        check(v);
    }
}

int BFS() {
    memset(dis,0x3f,sizeof(dis));
    q.push( (E){0,g,h,0,0} );
    while(!q.empty()) {
        E u = q.top(); q.pop();
        if(u.i==s && u.j==t) return u.d;    //终于到终点了！
        for(int k=0;k<4;k++) {              //4个方向 
            E v; 
            v.lou = u.lou; 
            v.hua = u.hua;
            v.i = u.i + ff[k];
            v.j = u.j + gg[k];             //下一个点的信息 
            int NB = getNB(v);
            if(v.i<0 || v.j<0 || v.i>n || v.j>m) continue;  //边界 
            int cl = z[v.i][v.j];           
            if(cl=='1') {
                v.d = u.d + 1;
                if(NB==2) check(v);         //楼观剑砍墙 
            }
            if(cl=='0' || cl=='X') {        //注意：‘X’是可以穿的！
                v.d = u.d + 1;
                check(v);
            }
            if(cl=='2') {
                if(NB!=0) v.d = u.d + 1;
                else      v.d = u.d + 4;    //不同NB值状态下距离不同。 
                check(v);
            }
            if(cl=='3') {
                if(NB!=0) v.d = u.d + 1;
                else      v.d = u.d + 9; 
                check(v);
            }
            if(cl=='4') {
                v.d = u.d + 1; v.hua = 1;   //偷花。
                check(v);
            }
            if(cl=='5') {                   //注意楼观剑要check两次，因为可以不选。 
                v.d = u.d + 1; 
                check(v); 
                if(!v.lou) v.lou = 1, v.d += 5;           //获得需5秒 
                check(v);
            }
        }
        if(z[u.i][u.j]=='X') jian_xi(u);                  //从间隙飞 
    }
    return -1;
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",z[i]+1);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) {
        if(z[i][j]=='M') z[i][j] = '0';                  //把麻薯变成0藏起来，别让幽幽子吃了。 
        if(z[i][j]=='S') g = i, h = j, z[i][j] = '0';    //注意起点是可以走好几次的，它的属性改成0。
        if(z[i][j]=='E') s = i, t = j, z[i][j] = '0';    
    }
    int ans = BFS();
    if(ans!=-1) printf("%d",ans);
    else printf("We want to live in the TouHou World forever");    //此生无悔入东方，来世炸了幻想乡。 
    return 0;
}

看起来长，其实很瘦的，压下行就短了:)