[P1979][NOIP2013] (BFS建图+SPFA)

#include<iostream> 
#include<cstring> 
#include<string> 
#include<algorithm> 
#include<cstdio> 
#include<queue> 
#define pr pair<int ,int >
using namespace std;
const int N = 233333;
const int inf = 0x3f3f3f3f;

int n,m,q;
int map[35][35],a[35][35],s[35][35][4][4];
int ex,ey,sx,sy,tx,ty,ans;
int dx[]={1,-1,0,0},dy[]={0,0,-1,1};
struct node{
    int x,y,dir;
}nd[N];
int head[N],cnt,l,r;
int vis[35][35][4],f[35][35][4];

void bfs(int x,int y,int op){
//op==1,表示是预处理 s数组 ;op==0，表示是在预处理开始时空白块移动到目标棋子四周的最小距离 
    queue<pr> q;
    memset(a,inf,sizeof(a));
    if(op) a[x][y]=1;
    else a[x][y]=0;
    q.push(pr(x,y));
    while(!q.empty()){
        int xx=q.front().first,yy=q.front().second;
        q.pop();
        for(int i=0;i<4;++i){
            int fx=xx+dx[i],fy=yy+dy[i];
            if(map[fx][fy]==0||fx<1||fx>n||fy<1||fy>m) continue;
            if(a[fx][fy]==inf) a[fx][fy]=a[xx][yy]+1,q.push(pr(fx,fy));
        }
    }
}

void deal(){
    memset(s,inf,sizeof(s));
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j){
        if(map[i][j]){
            for(int k=0;k<4;++k){
                int x=i+dx[k],y=j+dy[k];
                if(x<1||x>n||y<1||y>m) continue;
                if(map[x][y]){
                    map[x][y]=0;
                    bfs(i,j,1);
                    map[x][y]=1;
                    for(int l=0;l<4;++l){
                        int fx=x+dx[l],fy=y+dy[l];
                        if(fx<1||fx>n||fy<1||fy>m) continue;
                        if(a[fx][fy]<inf) s[i][j][k][l]=a[fx][fy];
                    }
                }
            }
        }
    }
}

void spfa(){
    while(l<=r){
        int x=nd[l].x,y=nd[l].y,d=nd[l].dir;//目标方块 
        int fx=x+dx[d],fy=y+dy[d];//空白方块 
        vis[x][y][d]=0;
        for(int i=0;i<4;++i){
            if(s[x][y][d][i]!=inf&&f[fx][fy][i]>f[x][y][d]+s[x][y][d][i]){
                f[fx][fy][i]=f[x][y][d]+s[x][y][d][i];
                if(!vis[fx][fy][i]){
                    vis[fx][fy][i]=1;
                    nd[++r].x=fx,nd[r].y=fy,nd[r].dir=i;
                }
            }
        }
        l++;
    }
}

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",&map[i][j]);
    deal();
    while(q--){
        scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
        if(sx==tx&&sy==ty){ puts("0");continue; }
        map[sx][sy]=0;
        bfs(ex,ey,0);
        map[sx][sy]=1;
        l=1,r=0;
        memset(f,inf,sizeof(f));
        memset(vis,0,sizeof(vis));
        for(int i=0;i<4;++i){
            int fx=sx+dx[i],fy=sy+dy[i];
            if(fx<1||fx>n||fy<1||fy>m) continue;
            if(a[fx][fy]<inf){
                nd[++r].x=sx;
                nd[r].y=sy;
                nd[r].dir=i;
                f[sx][sy][i]=a[fx][fy];
                vis[sx][sy][i]=1;
            }
        }
        spfa();
        ans=inf;
        for(int i=0;i<4;++i) ans=min(ans,f[tx][ty][i]);
        if(ans==inf) printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}