P16295 [蓝桥杯 2026 省 Java A 组] 勇闯迷宫 题解

· · 题解

挑战最短题解（？）。但我觉得这样说能听懂啊 /kel。

明显的分层图。

与以往不同的是，这里要分成 2P 个层，P 是环境状态，那个 2 表示当前用过了或还没用技能。

也就是说，dis_{i,j,k,0/1} 表示当前到达格子 (i,j)，环境状态为 0 \le k < P，且没用或用了技能的情况下的最少步数。

于是就可以做了。发现每次路径的权值有 0 和 1 这两种，普通 BFS 是行不通的。但是 Dijkstra 又大材小用了，其实并非大材小用而是因为带 \log 太慢了过不去（诶 2 \times 10^8 左右没道理三秒跑不过啊 TAT）。于是这里使用 01-BFS（不会的话左转 OI-wiki 学习）解决。

于是就做完了，最终的时间复杂度是 O(nmP) 的 qwq。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 305;
struct node{
    int x,y,val,is,p;
};
int n,m,P,Sx,Sy,Ex,Ey,a[N][N];
char c[N][N];
int dis[2][N][N][105],Ans;
int dx[]={1,0,-1,0,0},dy[]={0,1,0,-1,0};
//最后一栏的状态是【当前状态】
//下一次的状态要增加
//换句话说最开始在起点时状态为 P-1
deque<node> q;
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
void BFS_qwq(){
    memset(dis,0x3f,sizeof(dis));
    while(!q.empty())q.pop_back();
    dis[0][Sx][Sy][P-1]=0;
    q.push_front({Sx,Sy,0,0,P-1});
    while(!q.empty()){
        int x=q.front().x,y=q.front().y;
        int val=q.front().val;
        int is=q.front().is,p=q.front().p;
        q.pop_front();//弹出
        for(int i=0;i<5;i++){//五种状态是因为还可以留在原地
            int x2=x+dx[i],y2=y+dy[i];
            if(x2<1||x2>n||y2<1||y2>m)continue;
            if(c[x2][y2]=='#')continue;
            int pp=(p+1)%P;//新状态
            int nxval=val+(pp!=a[x2][y2]);//新的代价
            if(dis[is][x2][y2][pp]>nxval){
                dis[is][x2][y2][pp]=nxval;
                if(pp==a[x2][y2])q.push_front({x2,y2,nxval,is,pp});//入队
                else q.push_back({x2,y2,nxval,is,pp});//入队
            }
            if(!is){//可以考虑使用技能
                int p2=a[x2][y2];
                int nval=val+1;
                if(dis[1][x2][y2][p2]>nval){
                    dis[1][x2][y2][p2]=nval;
                    q.push_back({x2,y2,nval,1,p2});//入队
                }
            }
        }
    }return;
}
int main(){
    n=read(),m=read(),P=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>c[i][j];
            if(c[i][j]=='S')Sx=i,Sy=j;
            if(c[i][j]=='T')Ex=i,Ey=j;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)a[i][j]=read();
    BFS_qwq();
    Ans=0x3f3f3f3f;
    for(int i=0;i<P;i++)
        Ans=min(Ans,dis[0][Ex][Ey][i]),
        Ans=min(Ans,dis[1][Ex][Ey][i]);
    cout<<(Ans==0x3f3f3f3f?-1:Ans)<<"\n";
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！