Problem

https://www.luogu.org/problemnew/show/P1979

Solution

朴素算法是 $O(qn^4)$ 的 BFS，能过约 80 分。

考虑若目标棋子需要移动，则空白格子一定与目标棋子相邻。

因此设计状态 $(x, y, g)$，表示空白棋子与目标棋子 $(x, y)$ 相邻的的方向。

预处理 $(x, y, g_1, g_2)$，代表状态 $(x, y, g_1)$ 到 $(x, y, g_2)$ 的最少步数。

查询时先 BFS 到达与目标棋子相邻的状态，再 SPFA 在该状态上最短路即可。

为什么用 SPFA？

因为当年 SPFA 还没死（逃

理论复杂度 $O(4n^4+qn^3)$

Code

// Code by ajcxsu
// Problem: chess road

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
using namespace std;

const int N=31;
int mp[N][N];
int e[N][N][4][4];
int dist[N][N][4];
char S[N][N][4];

int mv[]={0, 1, 0, -1, 0};
int opp[]={2, 3, 0, 1};
int n, m;
bool valid(int x, int y) { return x>=1 && x<=n && y>=1 && y<=m && mp[x][y]; }
struct Dot { int x, y, g; } ;
queue<Dot> qu;
int dis[N][N];
void bfs(int x, int y, int g) {
    CLR(dis, 0x3f);
    if(!valid(x+mv[g], y+mv[g+1])) return;
    mp[x][y]=0;
    qu.push({x+mv[g], y+mv[g+1]});
    dis[x+mv[g]][y+mv[g+1]]=0;
    Dot na;
    int nx, ny;
    while(!qu.empty()) {
        na=qu.front(), qu.pop();
        for(int i=0;i<4;i++) {
            nx=na.x+mv[i], ny=na.y+mv[i+1];
            if(valid(nx, ny) && dis[nx][ny]>dis[na.x][na.y]+1) {
                dis[nx][ny]=dis[na.x][na.y]+1;
                qu.push({nx, ny});
            }
        }
    }
    for(int i=0;i<4;i++)
        e[x][y][g][i]=dis[x+mv[i]][y+mv[i+1]];
    mp[x][y]=1;
}

int SPFA(int sx, int sy, int ex, int ey, int tx, int ty) {
    if(ex==tx && ey==ty) return 0;
    CLR(dist, 0x3f);
    CLR(dis, 0x3f);
    mp[ex][ey]=0;
    qu.push({sx, sy});
    dis[sx][sy]=0;
    Dot na;
    int nx, ny, ng;
    while(!qu.empty()) {
        na=qu.front(), qu.pop();
        for(int i=0;i<4;i++) {
            nx=na.x+mv[i], ny=na.y+mv[i+1];
            if(valid(nx, ny) && dis[nx][ny]>dis[na.x][na.y]+1) {
                dis[nx][ny]=dis[na.x][na.y]+1;
                qu.push({nx, ny});
            }
        }
    }
    mp[ex][ey]=1;
    for(int i=0;i<4;i++) if(valid(ex+mv[i], ey+mv[i+1])) {
        dist[ex][ey][i]=dis[ex+mv[i]][ey+mv[i+1]], qu.push({ex, ey, i}),
        S[ex][ey][i]=1;
    }
    while(!qu.empty()) {
        na=qu.front(), qu.pop(); S[na.x][na.y][na.g]=0;
        for(int i=0;i<4;i++) {
            nx=na.x+mv[i], ny=na.y+mv[i+1], ng=opp[i];
            if(valid(nx, ny) && dist[nx][ny][ng]>dist[na.x][na.y][na.g]+e[na.x][na.y][na.g][i]+1) {
                dist[nx][ny][ng]=dist[na.x][na.y][na.g]+e[na.x][na.y][na.g][i]+1;
                if(!S[nx][ny][ng]) qu.push({nx, ny, ng});
            }
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<4;i++) ans=min(ans, dist[tx][ty][i]);
    return ans;
}

int main() {
    CLR(e, 0x3f);
    ios::sync_with_stdio(false), cin.tie(0);
    int q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) cin>>mp[i][j];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) if(mp[i][j])
        for(int k=0;k<4;k++) bfs(i, j, k);
    int a, b, c, d, e, f, res;
    while(q--) {
        cin>>a>>b>>c>>d>>e>>f;
        cout<<((res=SPFA(a, b, c, d, e, f))==0x3f3f3f3f?-1:res)<<endl;
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-1979.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆