题解：P12684 【MX-J15-T4】叉叉学习魔法

YGBC_ · 2026-10-24 14:30:17 · 题解

不一样的做法。

发现不能带 \log，考虑广搜，发现一次走的路可能为 0，考虑 0-1 BFS，发现你直接写 0-1 BFS 是错的，为什么呢？

记一个节点的状态为 (d,m)，其中 d 表示步数，m 表示魔法次数，发现你的搜索算法正确的充要条件就是你每次取出的节点状态满足弱偏序，即 d_1<d_2\vee (d_1=d_2 \wedge m_1<m_2)。如果直接 0-1 BFS 就不能保证第二关键字偏序，我们考虑优化：维护两个队列 q_1,q_2，如果用魔法就把新状态压入 q1，否则压入 q2，每次在两个队列中找最小的，这样可以保证每次取出的状态不降，正确性显然。

代码非常好写。

#include<bits/stdc++.h>
using namespace std;
constexpr int X=5005, inf=0x3f3f3f3f;
constexpr int dx[9]={0,-1,-1,1,1,-1,0,0,1};
constexpr int dy[9]={0,-1,1,-1,1,0,-1,1,0};

int N,M,dis[X][X],mn[X][X];
bool vis[X][X],mp[X][X];
pair<int,int> S,T;
queue<pair<int,int>> q1,q2;

inline pair<int,int> get_min()
{
    pair<int,int> res(inf,inf);

    if(q1.empty()){
        res=q2.front(); q2.pop();
    }
    else if(q2.empty()){
        res=q1.front(); q1.pop();
    }
    else{
        pair<int,int> C1=q1.front();
        pair<int,int> C2=q2.front();
        if(dis[C1.first][C1.second]>dis[C2.first][C2.second]){
            res=C2, q2.pop();
        }
        else if(dis[C1.first][C1.second]<dis[C2.first][C2.second]){
            res=C1, q1.pop();
        }
        else{
            if(mn[C1.first][C1.second]<mn[C2.first][C2.second]){
                res=C1, q1.pop();
            }
            else{
                res=C2, q2.pop();
            }
        }
    }

    return res;
}



void BFS()
{
    memset(dis,0x3f,sizeof dis);
    memset(mn,0x3f,sizeof mn);

    q1.emplace(S);

    dis[S.first][S.second]=mn[S.first][S.second]=0;

    while(!q1.empty()||!q2.empty()){
        auto C=get_min();
        int x=C.first, y=C.second;
        if(vis[x][y]) continue;
        vis[x][y]=1;
        for(int i=1;i<=4;i++){
            int nx=x+dx[i], ny=y+dy[i];
            if(vis[nx][ny]) continue;
            if(mp[nx][ny]) continue;
            if(nx<1||nx>N||ny<1||ny>M) continue;
            if(dis[nx][ny]<dis[x][y]) continue;
            if(dis[nx][ny]==dis[x][y]&&mn[nx][ny]<=mn[x][y]+1) continue;
            dis[nx][ny]=dis[x][y];
            mn[nx][ny]=mn[x][y]+1;
            q1.emplace(nx,ny);
        }
        for(int i=5;i<=8;i++){
            int nx=x+dx[i], ny=y+dy[i];
            if(vis[nx][ny]) continue;
            if(mp[nx][ny]) continue;
            if(nx<1||nx>N||ny<1||ny>M) continue;
            if(dis[nx][ny]<dis[x][y]+1) continue;
            if(dis[nx][ny]==dis[x][y]+1&&mn[nx][ny]<=mn[x][y]) continue;
            dis[nx][ny]=dis[x][y]+1;
            mn[nx][ny]=mn[x][y];
            q2.emplace(nx,ny);
        }
    }
}


signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>N>>M;
    for(int i=1;i<=N;i++){
        string s; cin>>s;
        for(int j=1;j<=M;j++){
            if(s[j-1]=='#') mp[i][j]=1;
            if(s[j-1]=='X') S={i,j};
            if(s[j-1]=='W') T={i,j};
        }
    }
    BFS();

    if(dis[T.first][T.second]==0x3f3f3f3f){
        cout<<-1<<' '<<-1;
    }
    else{
        cout<<dis[T.first][T.second]<<' '<<mn[T.first][T.second];
    }
}