题面

解题思路

分层图跑最短路加优化

分析

显然分层图跑一跑就好了

用 d[x][y][s][f] 表示到 $(x,y)$ ，状态为 $(sword,flower)$ 的最短路

主要考虑传送门

用 $Dijkstra$ 做的话只要某一个传送门最优，其他传送门肯定可以被这个传送门更新，也就是说，如果我们以 $(sword,flower)$ 的状态走到某个传送门，由于传送门是互相连通的，因此，其他传送门肯定能被更新，所以我们只要对于对于到达传送门的每个不同状态更新一次就可以了，这样就能在 $O(nmlog)$ 的不正确时间内跑出答案（出题人懒得卡

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define M 1000003
#define N 1003
using namespace std;
int Cx[4]={1,0,0,-1};
int Cy[4]={0,1,-1,0};
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct node{
    int x,y;
    node(int a,int b):x(a),y(b){}
    node(){}
}P[M];
struct stus{
    int x,y,s,f,cost;
    stus(int a,int b,int c,int d,int e):x(a),y(b),s(c),f(d),cost(e){}
    stus(){}
    inline bool operator< (const stus x) const{
        return cost>x.cost;
    }
}c;
int n,m,t,d[N][N][2][2],Sx,Sy,Ex,Ey,ans;
char b[N][N];bool v[N][N][2][2];
bool vis[2][2];
inline void Dijstra() {
    rint i,x,y,s,f,cost,Tx,Ty;
    priority_queue<stus>p;
    memset(d,inf,sizeof(d));
    p.push(stus(Sx,Sy,0,0,0));
    d[Sx][Sy][0][0]=0;
    while(!p.empty()) {
        c=p.top(),p.pop();
        x=c.x,y=c.y,s=c.s,f=c.f;
        if(v[x][y][s][f]) continue;v[x][y][s][f]=1;
        if(x==Ex&&y==Ey) return;
        if(b[x][y]=='X'&&!vis[s][f]) {//有不同的状态才转移
            vis[s][f]=1,cost=d[x][y][s][f]+1;
            for(i=1;i<=t;i++) {
                Tx=P[i].x,Ty=P[i].y;
                if(d[Tx][Ty][s][f]>cost) {
                    d[Tx][Ty][s][f]=cost,
                    p.push(stus(Tx,Ty,s,f,cost));
                }
            }
        }
        if(b[x][y]=='5'&&!s) {//拿剑的情况
            cost=d[x][y][s][f]+5;
            if(d[x][y][s|1][f]>cost) {
                d[x][y][s|1][f]=cost,
                p.push(stus(x,y,s|1,f,cost));
            }
        }
        if(b[x][y]=='4'&&!f) {//拿花的情况
            cost=d[x][y][s][f];
            if(d[x][y][s][f|1]>cost) {
                d[x][y][s][f|1]=cost,
                p.push(stus(x,y,s,f|1,cost));
            }
        }
        for(i=0;i<4;i++) {//向四周走
            Tx=x+Cx[i],Ty=y+Cy[i];
            if(b[Tx][Ty]==' ') continue;
            if(b[Tx][Ty]=='X'&&v[Tx][Ty][s][f]) continue;
            if(b[Tx][Ty]=='1') {
                if(s) {
                    cost=d[x][y][s][f]+1;
                    if(d[Tx][Ty][s][f]>cost) {
                        d[Tx][Ty][s][f]=cost,
                        p.push(stus(Tx,Ty,s,f,cost));
                    }
                }continue;
            }
            cost=d[x][y][s][f]+1;
            if(b[Tx][Ty]=='2') {if(!(s|f)) cost+=3;}
            if(b[Tx][Ty]=='3') {if(!(s|f)) cost+=8;}
            if(d[Tx][Ty][s][f]>cost) {
                d[Tx][Ty][s][f]=cost,
                p.push(stus(Tx,Ty,s,f,cost));
            }
        }
    }
}
int main()
{
    rint i,j;
    n=read(),m=read();
    for(i=1;i<=n;i++) {
        scanf("%s",b[i]+1);
        for(j=1;j<=m;j++) {
            if(b[i][j]=='X') P[++t]=node(i,j);
            if(b[i][j]=='S') Sx=i,Sy=j;
            if(b[i][j]=='E') Ex=i,Ey=j;
        }
    }
    for(i=1;i<=n;i++) b[i][0]=b[i][m+1]=' ';
    for(i=1;i<=m;i++) b[0][i]=b[n+1][i]=' ';Dijstra();
    ans=min(d[Ex][Ey][0][0],d[Ex][Ey][0][1]);
    cmin(ans,min(d[Ex][Ey][1][0],d[Ex][Ey][1][1]));
    if(ans<inf) printf("%d",ans);
    else printf("We want to live in the TouHou World forever");
    return 0;
}

devil.