NOIP 华容道

思路

设为坐标(i,j)点不动，白点从(i,j)四个方向上的某个方向x转移到y的最小代价。

*1*
2+3
*4*

就是坐标点，1~4就是四个可能的位置。
然后愉快的跑spfa就可以了，具体的增光看代码就很清晰了。

代码

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int f[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int n,m,Q,a[31][31];
int dp[31][31][4][4];
int q[4010],l,r,vis[31][31];
int x,y,xx,yy,cc;
int bfs(int X,int Y,int sx,int sy,int tx,int ty) {
    if (sx>n||sx<1||sy>m||sy<1||tx>n||tx<1||ty>m||ty<1) return inf;
    if (!a[sx][sy]||!a[tx][ty]||!a[X][Y]) return inf;   
    memset(vis,0,sizeof(vis));
    l=1;r=2;q[1]=sx;q[2]=sy;vis[sx][sy]=1;vis[X][Y]=1;
    while (l<=r) {
        x=q[l++];y=q[l++];
        if (x==tx&&y==ty) return vis[x][y]-1;
        for (int k=0;k<4;k++) {
            xx=x+f[k][0];yy=y+f[k][1];
            if (!vis[xx][yy]&&a[xx][yy])
                vis[xx][yy]=vis[x][y]+1,q[++r]=xx,q[++r]=yy;
        }
    }
    return inf; 
}
void getdp() {
    int sx,sy,tx,ty;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            for (int k=0;k<4;k++)
                for (int c=0;c<4;c++) {
                    sx=i+f[k][0];sy=j+f[k][1];tx=i+f[c][0];ty=j+f[c][1];
                    dp[i][j][k][c]=bfs(i,j,sx,sy,tx,ty);
                }
}
int dis[31][31][4];
int EX,EY,SX,SY,TX,TY,ret;
int in[31][31][4];
void spfa() {
    memset(in,0,sizeof(in));l=1;r=0;
    for (int i=0;i<4;i++) 
    if (dis[SX][SY][i]!=inf) in[SX][SY][i]=1,q[++r]=SX,q[++r]=SY,q[++r]=i;
    while (l<=r) {
        x=q[l++];y=q[l++];cc=q[l++];
        for (int i=0;i<4;i++) {
            if (dis[x][y][i]>dis[x][y][cc]+dp[x][y][cc][i]) {
                dis[x][y][i]=dis[x][y][cc]+dp[x][y][cc][i];
                if (!in[x][y][i])q[++r]=x,q[++r]=y,q[++r]=i;
            }
        }
        if (dis[x+f[cc][0]][y+f[cc][1]][cc^1]>dis[x][y][cc]+1) {
            dis[x+f[cc][0]][y+f[cc][1]][cc^1]=dis[x][y][cc]+1;
            if (!in[x+f[cc][0]][y+f[cc][1]][cc^1]) 
                q[++r]=x+f[cc][0],q[++r]=y+f[cc][1],q[++r]=cc^1;
        }
    }
    ret=min(dis[TX][TY][1],min(dis[TX][TY][2],min(dis[TX][TY][3],dis[TX][TY][0])));
    if (ret==inf) puts("-1");
    else printf("%d\n",ret);
}
int main() {
    scanf("%d%d%d",&n,&m,&Q);
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&a[i][j]);
    memset(dp,0x3f,sizeof(dp));
    getdp();
    while (Q--) {
        scanf("%d%d%d%d%d%d",&EX,&EY,&SX,&SY,&TX,&TY);
        if (SX==TX&&SY==TY) {puts("0");continue;}
        if (!a[EX][EY]||!a[SX][SY]||!a[TX][TY]) {puts("-1");continue;}
        memset(dis,0x3f,sizeof(dis));
        for (int i=0;i<4;i++) 
            dis[SX][SY][i]=ret=bfs(SX,SY,EX,EY,SX+f[i][0],SY+f[i][1]);
        spfa();
    }
}