noip2013day2-华容道

题目描述

小 (B) 最近迷上了华容道，可是他总是要花很长的时间才能完成一次。于是，他想到用编程来完成华容道：给定一种局面，华容道是否根本就无法完成，如果能完成，最少需要多少时间。

小 (B) 玩的华容道与经典的华容道游戏略有不同，游戏规则是这样的：

在一个 (n*m) 棋盘上有 (n*m) 个格子，其中有且只有一个格子是空白的，其余 (n*m-1)个格子上每个格子上有一个棋子，每个棋子的大小都是 $1*1 $的；
有些棋子是固定的，有些棋子则是可以移动的；
任何与空白的格子相邻（有公共的边）的格子上的棋子都可以移动到空白格子上。游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。

给定一个棋盘，游戏可以玩 (q) 次，当然，每次棋盘上固定的格子是不会变的，但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第$ i$ 次玩的时候，空白的格子在第$ EX_i$ 行第 (EY_i) 列，指定的可移动棋子的初始位置为第 (SX_i) 行第 (SY_i) 列，目标位置为第 (TX_i) 行第 (TY_i) 列。

假设小 (B) 每秒钟能进行一次移动棋子的操作，而其他操作的时间都可以忽略不计。请你告诉小 (B) 每一次游戏所需要的最少时间，或者告诉他不可能完成游戏。

Input

第一行有 (3) 个整数，每两个整数之间用一个空格隔开，依次表示 (n、m) 和$ q$；

接下来的$ n$ 行描述一个 (n*m) 的棋盘，每行有 (m) 个整数，每两个整数之间用一个空格隔开，每个整数描述棋盘上一个格子的状态，(0) 表示该格子上的棋子是固定的，(1) 表示该格子上的棋子可以移动或者该格子是空白的。

接下来的 (q) 行，每行包含 (6) 个整数依次是 (EX_i、EY_i、SX_i、SY_i、TX_i、TY_i)，每两个整数之间用一个空格隔开，表示每次游戏空白格子的位置，指定棋子的初始位置和目标位置。

(100\%)的数据，(1 ≤ n, m ≤ 30，q ≤ 500。)

Output

输出有 (q) 行，每行包含$ 1 (个整数，表示每次游戏所需要的最少时间，如果某次游戏无法完成目标则输出)−1$

Sample Input

3 4 2
0 1 1 1
0 1 1 0
0 1 0 0
3 2 1 2 2 2
1 2 2 2 3 2

Sample Output

2
-1

很显然，看到这道题的第一眼就想到了广搜。

每次，只用记录空白块以及指定块的位置，直接广搜。

然而，我们仔细算一下时间复杂度(O(q*(n*m)^2))。

不能愉快的过掉此题。。。。

考虑优化，我们发现：

1.指定块能移动到指定位置当且仅当空白块在指定块边上。

2.当指定块移动时，必定是空白块到了指定块的另一边，在进行交换。

并且，这些状态的转移步数在指定块固定时可以直接广搜得到。

于是我们考虑，对那些状态进行建图，建完图后进行连边。

那么如何对这些状态进行建图呢？

之前，我们发现只有空白块在指定块的四周才有用，只有这才是有效状态。

所以，我们定义一个有效状态为:

空白块在指定块的上下左右。

于是，我们就可以很方便的对一个状态进行哈希，一个状态的哈希函数为：

inline int Id(int x,int y,int cnt){
    return 120*x+4*y+cnt;//x,y为指定块的所在的位置，cnt为空白块在指定块的上下左右的位置
}

定义出了哈希函数后，我们可以对两个状态进行连边，很显然，对于一个有效状态，其后续状态有四个：

为空白块在其他的三个方向，以及空白块和指定块交换（这个状态的边权是一）。

于是，我们对每个状态进行广搜建图，连边。

最后，对于每个询问直接在建好的图上跑最短路即可。

代码如下

#include <bits/stdc++.h>
 
using namespace std;
 
#define LL long long
#define u64 unsigned long long
#define u32 unsigned int
#define reg register
#define Raed Read
#define debug(x) cerr<<#x<<" = "<<x<<endl;
#define rep(a,b,c) for(reg int a=(b),a##_end_=(c); a<=a##_end_; ++a)
#define ret(a,b,c) for(reg int a=(b),a##_end_=(c); a<a##_end_; ++a)
#define drep(a,b,c) for(reg int a=(b),a##_end_=(c); a>=a##_end_; --a)
#define erep(i,G,x) for(int i=(G).Head[x]; i; i=(G).Nxt[i])
 
inline int Read() {
    int res = 0, f = 1;
    char c;
    while (c = getchar(), c < 48 || c > 57)if (c == '-')f = 0;
    do res = (res << 3) + (res << 1) + (c ^ 48);
    while (c = getchar(), c >= 48 && c <= 57);
    return f ? res : -res;
}
 
template<class T>inline bool Min(T &a, T const&b) {
    return a > b ? a = b, 1 : 0;
}
template<class T>inline bool Max(T &a, T const&b) {
    return a < b ? a = b, 1 : 0;
}
 
const int N=35,M=4505;
const int dx[4]= {1,-1,0,0},dy[4]= {0,0,1,-1};
 
bool MOP1;
 
int n,m,q,A[N][N];
 
struct Link_list {
    int Tot,Head[M],cost[M<<1],to[M<<1],Nxt[M<<1];
    inline void clear(void) {
        Tot=0;
        memset(Head,0,sizeof Head);
    }
    inline void AddEdge(int a,int b,int c) {
        to[++Tot]=b,cost[Tot]=c,Nxt[Tot]=Head[a],Head[a]=Tot;
    }
} G;
 
inline int Id(int x,int y,int cnt) {
    return 120*x+4*y+cnt;
}
 
struct T3Ac {
    struct node {
        int x,y;
    } Q[N*N*N*N];
    int dis[N][N];
    void bfs(int x1,int y1,int x2,int y2,int cnt) {
        memset(dis,0,sizeof dis);
        dis[x1][y1]=1;
        int L=0,R=0;
        Q[++R]=(node)<%x1,y1%>;
        while(L<R) {
            node Now=Q[++L];
            rep(i,0,3) {
                int Dx=dx[i]+Now.x,Dy=dy[i]+Now.y;
                if(Dx<1||Dy<1||Dx>n||Dy>m)continue;
                if(Dx==x2&&Dy==y2)continue;
                if(!A[Dx][Dy])continue;
                if(dis[Dx][Dy])continue;
                dis[Dx][Dy]=dis[Now.x][Now.y]+1;
                Q[++R]=(node)<%Dx,Dy%>;
            }
        }
        if(!(cnt^4))return;
        rep(i,0,3) {
            int Dx=dx[i]+x2,Dy=dy[i]+y2;
            if(Dx<1||Dy<1||Dx>n||Dy>m)continue;
            if(Dx==x1&&Dy==y1)continue;
            if(!dis[Dx][Dy])continue;
            G.AddEdge(Id(x2,y2,cnt),Id(x2,y2,i),dis[Dx][Dy]-1);
        }
        G.AddEdge(Id(x2,y2,cnt),Id(x1,y1,cnt^1),1);
    }
    int vis[M],D[M],q1[N*N*N*N];
    void spfa(int x1,int y1) {
        int L=0,R=0;
        memset(D,63,sizeof D);
        memset(vis,0,sizeof vis);
        rep(i,0,3) {
            int Dx=dx[i]+x1,Dy=dy[i]+y1;
            if(Dx<1||Dy<1||Dx>n||Dy>m)continue;
            if(!dis[Dx][Dy])continue;
            D[Id(x1,y1,i)]=dis[Dx][Dy]-1,vis[Id(x1,y1,i)]=1;
            q1[++R]=Id(x1,y1,i);
        }
        while(L<R) {
            int x=q1[++L];
            vis[x]=0;
            erep(i,G,x) {
                int y=G.to[i],z=G.cost[i];
                if(D[y]>D[x]+z) {
                    D[y]=D[x]+z;
                    if(!vis[y])vis[y]=1,q1[++R]=y;
                }
            }
        }
    }
    inline void solve(void) {
        rep(i,1,n)rep(j,1,m)A[i][j]=Read();
        rep(i,1,n)rep(j,1,m) {
            if(!A[i][j])continue;
            rep(k,0,3) {
                int Dx=dx[k]+i,Dy=dy[k]+j;
                if(A[Dx][Dy])bfs(Dx,Dy,i,j,k);
            }
        }
        rep(i,1,q) {
            int ex=Read(),ey=Read(),sx=Read(),sy=Read(),tx=Read(),ty=Read();
            if(sx==tx&&sy==ty) {
                puts("0");
                continue;
            }
            bfs(ex,ey,sx,sy,4);
            spfa(sx,sy);
            int Ans=1e9;
            rep(j,0,3)Min(Ans,D[Id(tx,ty,j)]);
            if(Ans<1e9)printf("%d
",Ans);
            else puts("-1");
        }
    }
} P100;
 
bool MOP2;
 
inline void _main(void) {
    n=Read(),m=Read(),q=Read();
    P100.solve();
}
 
signed main() {
#define offline1
#ifdef offline
    freopen("puzzle.in", "r", stdin);
    freopen("puzzle.out", "w", stdout);
    _main();
    fclose(stdin);
    fclose(stdout);
#else
    _main();
#endif
    return 0;
}