题解：P14469 [COCI 2025/2026 #1] 皇后 / Kraljica

· · 题解

首先这道题先考虑 bfs 做法，我们发现对于数字之间的传送是不需要任何花费的，所以可以将他们的边权设为 0，然而对于普通的点之间的边权就是 1，直接使用 01 BFS 即可通过。

因为我们第一次 bfs 到一个点就是最优答案，所以每个点规定经过一次，时间复杂度 O(n^2)。

代码比较难写，注意一些细节。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
bool Test_MLE_start;
constexpr int N=1001;
int _=1,n,m,sx,sy,fx,fy,x[10][2],y[10][2],dp[N][N];
char s[N][N];bool vis[N][N];
struct node {int x,y;};
deque<node> q;
inline int reads() {
    int c=getchar(),x=0,f=1;
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) {
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    return x*f;
}
inline void files() {
    freopen("std.in","r",stdin);
    freopen("std.out","w",stdout);
}
inline void clr() {
//  Don't forget!

}
void bfs(int sx,int sy) {
    memset(dp,0x3f,sizeof(dp));
    q.push_back(node {sx,sy});
    dp[sx][sy]=0;
    while(!q.empty()) {
        int idx=q.front().x,idy=q.front().y;
        q.pop_front();
        if(vis[idx][idy]) continue;
        vis[idx][idy]=1;
        for(int x=idx+1; x<=n; x++) {
            int y=idy;
            if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
            if(dp[x][y]>dp[idx][idy]+1){
                dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
                q.push_back(node {x,y});
            }
        }
        for(int x=idx-1; x>=1; x--) {
            int y=idy;
            if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
            if(dp[x][y]>dp[idx][idy]+1){
                dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
                q.push_back(node {x,y});
            }
        }
        for(int y=idy+1; y<=m; y++) {
            int x=idx;
            if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
            if(dp[x][y]>dp[idx][idy]+1){
                dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
                q.push_back(node {x,y});
            }
        }
        for(int y=idy-1; y>=1; y--) {
            int x=idx;
            if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
            if(dp[x][y]>dp[idx][idy]+1){
                dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
                q.push_back(node {x,y});
            }
        }
        for(int x=idx+1,y=idy+1; x<=n,y<=m; x++,y++) {
            if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
            if(dp[x][y]>dp[idx][idy]+1){
                dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
                q.push_back(node {x,y});
            }
        }
        for(int x=idx+1,y=idy-1; x<=n,y>=1; x++,y--) {
            if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
            if(dp[x][y]>dp[idx][idy]+1){
                dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
                q.push_back(node {x,y});
            }
        }
        for(int x=idx-1,y=idy+1; x>=1,y<=m; x--,y++) {
            if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
            if(dp[x][y]>dp[idx][idy]+1){
                dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
                q.push_back(node {x,y});
            }
        }
        for(int x=idx-1,y=idy-1; x>=1,y>=1; x--,y--) {
            if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
            if(dp[x][y]>dp[idx][idy]+1){
                dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
                q.push_back(node {x,y});
            }
        }
        if(isdigit(s[idx][idy])) {
            int p=s[idx][idy]-'0',px,py;
            if(idx==x[p][0]&&idy==y[p][0]) px=x[p][1],py=y[p][1];
            else px=x[p][0],py=y[p][0];
            dp[px][py]=min(dp[px][py],dp[idx][idy]);
            q.push_front(node {px,py});
        }
    }
}
bool Test_MLE_end;
signed main() {
//  printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//  files();
//  _=reads();
    while(_--) {
        clr();
        n=reads(),m=reads();
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                cin>>s[i][j];
                if(s[i][j]=='S') sx=i,sy=j;
                else if(s[i][j]=='E') fx=i,fy=j;
                else if(isdigit(s[i][j])) {
                    int p=s[i][j]-'0';
                    if(!x[p][0]) x[p][0]=i;
                    else x[p][1]=i;
                    if(!y[p][0]) y[p][0]=j;
                    else y[p][1]=j;
                }
            }
        }bfs(sx,sy);
        if(dp[fx][fy]==0x3f3f3f3f) puts("-1");
        else printf("%d\n",dp[fx][fy]);
    }
    return 0;
}
/*
5 5
S##..
##...
..#..
.....
.#..E
*/