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

题意：给出一张地图，分为可走和不可走，有 T次询问，每次给出 3对坐标，分别为空白格子，指定的可移动棋子，目标位置的初始坐标，求出将可移动棋子移动到目标位置的最小步数；

解法：BFS建图+SPFA；

1.BFS建图：

1. 首先可以想到，只有空格在目标棋子的旁边，才可以使目标棋子移动；

2. 进行一次移动后，空格要再次回到目标棋子旁边，才可以继续移动；

3. 而在移回的过程中，不可以经过目标棋子（否则会改变目标棋子的位置），这时相当于目标棋子是不可移动的；

4. 而对于同一个图，对于某个指定的棋子来讲，与它相邻的空格从某个方向移到某个方向之间要走的步数是一定的；

5. 所以可以预处理出对于某个指定的棋子，其临近的空格在不同状态之间转移的步数:f[x][y][i][j]，表示空格在目标棋子（x，y）的 i 方向上，当目标棋子与空白格交换后，空白格重新移动到目标棋子的新位置（x+dx[i],y+dy[i]）的 j 方向上的临近格子的最小步数（这个预处理要算上开始时的空白格与目标棋子交换的步数，即 +1，下面会有注释）

2.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;
}

View Code