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

· · 题解

先考虑第一问怎么求，我们将斜着的边权设为 0，直着的边权设为 1，那么相当于一个最短路问题，而且边权只有 0 和 1，可以通过 01bfs 来解决。当然，我们其实不需要把图建出来，直接在矩阵上做也可以。

然后我们来考虑怎么做第二问，第二问要求魔法使用最少，乍一看可以用类似的方法，但是这问有一个前提条件——要在使用最少步数的情况下。那么这个时候可以理解为不是所有的路都能走了，我们需要知道什么情况下这条边能走。

如果我们设 dis_{i,j} 表示从起点到 (i,j) 位置的最小步数，那么对于周围的 8 个格子中能走的格子之一 (p,q)，只有 dis_{p,q}=dis_{i,j}+w（其中如果为直边 w=1，否则为 0）的时候 (i,j) 到 (p,q) 的边才是能用的。这是因为如果我们走了 dis_{p,q}<dis_{i,j}+w 的边，那么这条边会使得我们的步数不是最小的（因为存在另一种到 (p,q) 的方式步数严格小于这种方式）。所以我们设置只有这样的边能走，并把直边设为 0，斜边设为 1，再做一遍 01bfs 即可。

时间复杂度：O(nm)。

#include<bits/stdc++.h>
#define N 5005
#define pi pair<int,int>
using namespace std;
int n,m,w[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
int sx,sy,tx,ty,dis[N][N],g[N][N];
bool vis[N][N];
char a[N][N];
deque<pi>q;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin>>a[i][j];
            if(a[i][j]=='X')sx=i,sy=j;
            if(a[i][j]=='W')tx=i,ty=j;
        }
    }
    memset(dis,0x3f,sizeof(dis));dis[sx][sy]=0;
    q.push_front({sx,sy});
    while(!q.empty()){
        pi c=q.front();q.pop_front();
        int x=c.first,y=c.second;
        if(vis[x][y])continue;
        vis[x][y]=1;
        //cout<<x<<" "<<y<<" "<<dis[x][y]<<'\n';
        for(int i=0;i<8;++i){
            int px=x+w[i][0],py=y+w[i][1];
            if(px>=1&&px<=n&&py>=1&&py<=m&&a[px][py]!='#'){
                if(dis[px][py]>dis[x][y]+(i<4)){
                    dis[px][py]=dis[x][y]+(i<4);
                    if(i<4)q.push_back({px,py});
                    else q.push_front({px,py});
                }
            }
        }
    }
    if(!vis[tx][ty])return cout<<"-1 -1",0;
//for(int i=1;i<=n;++i){
    //  for(int j=1;j<=m;++j)cout<<dis[i][j]<<" ";cout<<'\n';
    //}
    cout<<dis[tx][ty]<<" ";
    memset(g,0x3f,sizeof(g));g[sx][sy]=0;
    memset(vis,0,sizeof(vis));
    q.push_front({sx,sy});
    while(!q.empty()){
        pi c=q.front();q.pop_front();
        int x=c.first,y=c.second;
        if(vis[x][y])continue;
        vis[x][y]=1;
        for(int i=0;i<8;++i){
            int px=x+w[i][0],py=y+w[i][1];
            if(px>=1&&px<=n&&py>=1&&py<=m&&a[px][py]!='#'&&dis[px][py]==dis[x][y]+(i<4)){
                if(g[px][py]>g[x][y]+(i>=4)){
                    g[px][py]=g[x][y]+(i>=4);
                    if(i>=4)q.push_back({px,py});
                    else q.push_front({px,py});
                }
            }
        }
    }
    cout<<g[tx][ty];
    return 0;
}