[NOIP2013 提高组] 华容道
题意：
一个棋盘上，每个格子上都有一个 \(1 \times 1\) 的棋子，有些棋子固定，剩下的可以移动。棋子只能移动到空白的格子里。\(Q\) 次询问，每次给出空白格子的位置、目标棋子的位置以及终点的位置，问把目标棋子移动到终点的最小步数。无解输出 \(-1\)。
思路：
这类有少量空白和大量棋子的问题，一个很重要的想法就是把棋子的移动转化成空白的移动。然后发现，局面只和空白格的位置与目标棋子的位置有关系，那就可以 bfs 了，让空白格子随意动，目标棋子第一次到达终点的时间就是最短时间。这样有 70pts。
然后有个很重要的性质，就是局面的改变只会发生在空白格子与目标棋子相邻的时候，且一次改变后目标棋子只会向四个方向移动。如果我们把每个状态（不同的状态包括目标棋子与空白格子相对位置不同）都抽象成结点，然后把状态的改变看做边，花费的步数看作边权，则就可以用最短路求解了。求边权的过程用 bfs 即可。
代码：
#include<bits/stdc++.h>
namespace IO{
const int sz = 1<<22;
char a[sz+5], b[sz+5], *p1 = a, *p2 = a, *t = b, p[105];
char gc(){return p1 == p2?(p2 = (p1 = a)+fread(a, 1, sz, stdin), p1 == p2?EOF:*p1++):*p1++;}
template<class T>
void gi(T &x){
x = 0; char ch = gc();
while(ch<'0' || ch>'9') ch = gc();
while(ch>='0'&&ch<='9') x = x*10+(ch-48), ch = gc();
}
void flush(){fwrite(b, 1, t-b, stdout); t = b;}
void pc(char ch){*t++ = ch; if(t-b==sz) flush();}
template<class T>
void pi(T x, char ch = '\n'){
if(x == 0) pc('0');
if(x < 0) pc('-'), x = -x;
int tp = 0;
while(x){
p[++tp] = x%10+48;
x/=10;
}
while(tp){
pc(p[tp--]);
}
pc(ch);
}
struct F{~F(){flush();}}f;
}
using IO::gi;
using IO::pi;
//快读快写
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 35;
const int NN = 4000, MM = 120000;
struct node{
int nxt, to, w;
}edge[MM<<1];
int head[NN], tot;
void add(int u, int v, int w){
edge[++tot].nxt = head[u];
edge[tot].to = v;
edge[tot].w = w;
head[u] = tot;
}
struct point{
int x, y;
bool operator == (const point &b) const{
return x == b.x && y == b.y;
}
};
// point targ;
bool vis[N][N][N][N];//目标棋子x, y；空白格x, y。
int dx[4] = {0, 1, 0, -1};//0 1 2 3: 左上右下
int dy[4] = {-1, 0, 1, 0};
int mp[N][N];
int id[N][N][4], idx;
struct xwx{
int xw, yw, xt, yt;//白格，目标棋子。
int step;
bool operator == (const xwx &b) const{
return xw == b.xw && yw == b.yw && xt == b.xt && yt == b.yt;
}
};
xwx targ, stk[1000000];
int top;
int n, m, Q;
int del;
int bfs(xwx st){
if(st == targ) return 0;
while(top){
vis[stk[top].xt][stk[top].yt][stk[top].xw][stk[top].yw] = 0;
--top;
}
// memset(vis, 0, sizeof(vis));
queue<xwx> q;
q.push(st);
while(!q.empty()){
xwx tmp = q.front();
q.pop();
int tx, ty, nx = tmp.xt, ny = tmp.yt;
for(int o = 0; o<4; ++o){
tx = tmp.xw+dx[o], ty = tmp.yw+dy[o];
if((!mp[tx][ty]) || tx < 1 || tx > n || ty < 1 || ty > m) continue;
if(tx == nx && ty == ny){
if(vis[tmp.xw][tmp.yw][tx][ty]) continue;
vis[tmp.xw][tmp.yw][tx][ty] = 1;
xwx nxt = (xwx){tx, ty, tmp.xw, tmp.yw, tmp.step+1};
stk[++top] = nxt;
if(nxt == targ) return tmp.step+1;
q.push(nxt);
} else{
if(vis[nx][ny][tx][ty]) continue;
vis[nx][ny][tx][ty] = 1;
xwx nxt = (xwx){tx, ty, nx, ny, tmp.step+1};
stk[++top] = nxt;
if(nxt == targ) return tmp.step+1;
q.push(nxt);
}
}
}
return INF;
}
int dst[NN];
struct uwu{
int p; int dst;
bool operator <(const uwu &b) const{
return dst > b.dst;
}
};
priority_queue<uwu> q;
bool vs[NN];
void dij(int st){
memset(dst, 0x3f, sizeof(dst));
memset(vs, 0, sizeof(vs));
dst[st] = 0;
q.push((uwu){st, dst[st]});
while(!q.empty()){
int u = q.top().p;
q.pop();
if(vs[u]) continue;
vs[u] = 1;
for(int i = head[u]; i; i = edge[i].nxt){
int v = edge[i].to;
if(!vs[v] && dst[u] + edge[i].w < dst[v]){
dst[v] = dst[u] + edge[i].w;
q.push((uwu){v , dst[v]});
}
}
}
}
int main(){
gi(n), gi(m), gi(Q);
del = n+m;
for(int i = 1; i<=n; ++i){
for(int j = 1; j<=m; ++j){
gi(mp[i][j]);
}
}
for(int i = 1; i<=n; ++i){
for(int j = 1; j<=m; ++j){
int tx, ty;
for(int o = 0; o<4; ++o){
tx = i+dx[o], ty = j+dy[o];
if(tx<1 || tx>n || ty<1 || ty>m || (!mp[tx][ty])) continue;
id[i][j][o] = ++idx;
}
}
}
for(int i = 1; i<=n; ++i){
for(int j = 1; j<=m; ++j){//枚举目标块在哪里
int tx, ty;
for(int d = 1; d<3; ++d){
tx = i+dx[d], ty = j+dy[d];//枚举右和上方向相邻的方格。（转移到的下一步）
if(tx<1 || tx>n || ty<1 || ty>m || (!mp[tx][ty])) continue;
int stx, sty, ttx, tty;//枚举起点与终点空白格的位置。
for(int os = 0; os<4; ++os){
stx = i+dx[os], sty = j+dy[os];
if(stx<1 || stx>n || sty<1 || sty>m || (!mp[stx][sty])) continue;
for(int ot = 0; ot<4; ++ot){
ttx = tx+dx[ot], tty = ty+dy[ot];
if(ttx<1 || ttx>n || tty<1 || tty>m || (!mp[ttx][tty])) continue;
targ = (xwx){ttx, tty, tx, ty, 0};
int dst = bfs((xwx){stx, sty, i, j, 0});
if(dst!=INF){
add(id[i][j][os], id[tx][ty][ot], dst);
add(id[tx][ty][ot], id[i][j][os], dst);
}
}
}
}
}
}
int ex, ey, sx, sy, tx, ty;
while(Q--){
gi(ex), gi(ey), gi(sx), gi(sy);
gi(tx);gi(ty);
if(sx == tx && sy == ty){//如果就在终点则空白格子不用动，所以要特判。
IO::pc('0');
IO::pc('\n');
continue;
}
int stx, sty, ans = INF, fst;
for(int o = 0; o<4; ++o){
if(!id[sx][sy][o]) continue;
stx = sx+dx[o], sty = sy+dy[o];
targ = (xwx){stx, sty, sx, sy};
fst = bfs((xwx){ex, ey, sx, sy});//注意要先移动空白到目标棋子的附近。
dij(id[sx][sy][o]);
for(int ot = 0; ot<4; ++ot){
if(!id[tx][ty][ot]) continue;
ans = min(ans, fst+dst[id[tx][ty][ot]]);
}
}
if(ans == INF) ans = -1;
pi(ans, '\n');
}
return 0;
}