题解 (by;zjvarphi)
NOIP2013 的原题
最简单的思路就是一个 bfs，可以拿到 (70pts)
75pts
#include<bits/stdc++.h>
#define ri signed
#define pd(i) ++i
#define bq(i) --i
#define func(x) std::function<x>
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++
#define debug1(x) std::cerr << #x"=" << x << ' '
#define debug2(x) std::cerr << #x"=" << x << std::endl
#define Debug(x) assert(x)
struct nanfeng_stream{
template<typename T>inline nanfeng_stream &operator>>(T &x) {
bool f=false;x=0;char ch=gc();
while(!isdigit(ch)) f|=ch=='-',ch=gc();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
return x=f?-x:x,*this;
}
}cin;
}
using IO::cin;
namespace nanfeng{
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
static const int N=31;
static const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int n,m,q,ex,ey,sx,sy,tx,ty;
bool vis[N][N][N][N],est[N][N];
struct Que{int x,y,nx,ny,stp;}que[N*N*N*N];
auto bfs=[]() {
int hd=1,tl=0;
que[tl=1].x=ex,que[1].y=ey;
que[1].nx=sx,que[1].ny=sy;
while(hd<=tl) {
int x=que[hd].x,y=que[hd].y;
for (ri i(0);i<4;pd(i)) {
int stx=x+dx[i],sty=y+dy[i],nx=que[hd].nx,ny=que[hd].ny;
if (stx==nx&&sty==ny) nx=x,ny=y;
if (stx<1||stx>n||sty<1||sty>m||!est[stx][sty]||vis[stx][sty][nx][ny]) continue;
++tl;
que[tl].x=stx,que[tl].y=sty,que[tl].nx=nx,que[tl].ny=ny,que[tl].stp=que[hd].stp+1;
vis[stx][sty][nx][ny]=true;
if (nx==tx&&ny==ty) return que[tl].stp;
}
++hd;
}
return -1;
};
inline int main() {
// FI=freopen("y.in","r",stdin);
// FO=freopen("y.out","w",stdout);
cin >> n >> m >> q;
for (ri i(1);i<=n;pd(i))
for (ri j(1);j<=m;pd(j)) cin >> est[i][j];
for (ri z(1);z<=q;pd(z)) {
cin >> ex >> ey >> sx >> sy >> tx >> ty;
if (sx==tx&&sy==ty) printf("0
");
else {
memset(vis,false,sizeof(vis));
printf("%d
",bfs());
}
}
return 0;
}
}
int main() {return nanfeng::main();}
常数写小一点，再开个 (O2) 洛谷和 loj 就过了。
正解：
对于一个点，它能移动只有当它周围四个方向存在空格子时，所以一个思路就是先将空格子移动到初始格子周围，再向目标点移动，同时维护空格点的位置。
设 (move_{x,y,t1,t2}) 表示当前在 ((x,y)) 的格子，由空格子在它的左/上侧转移到右/下侧需要多少步，这个可以 bfs 预处理出来。
然后在询问时再用一个 bfs 处理出空格子到初始点的四个状态中所需要的步数。
设 (f_{x,y,t}) 表示点 ((x,y))，空格在它的 (t) 状态，由初始点转移过来要多少步。
转移就是 (f_{x,y,t}=min (f_{xx,yy,tt}+mv_{xx,yy,tt,i}+1))
其中 (t) 是 (i) 对称过去的状态，((x,y)) 是 ((xx,yy)) 周围的点。
最后跑一个最短路，特判一下无解。
Code
#include<bits/stdc++.h>
#define ri signed
#define pd(i) ++i
#define bq(i) --i
#define func(x) std::function<x>
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++
#define debug1(x) std::cerr << #x"=" << x << ' '
#define debug2(x) std::cerr << #x"=" << x << std::endl
#define Debug(x) assert(x)
struct nanfeng_stream{
template<typename T>inline nanfeng_stream &operator>>(T &x) {
bool f=false;x=0;char ch=gc();
while(!isdigit(ch)) f|=ch=='-',ch=gc();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
return x=f?-x:x,*this;
}
}cin;
}
using IO::cin;
namespace nanfeng{
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
static const int N=31;
static const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int mv[N][N][4][4],dis[N][N][4],n,m,q,ex,ey,sx,sy,tx,ty,cnt;
bool vis[N][N],vs[N][N][4],est[N][N];
struct Que{int x,y,d;}qe[N*N*N*N];
auto bfs=[](int x,int y,int f1,int f2) {
int sx=x+dx[f1],sy=y+dy[f1],tx=x+dx[f2],ty=y+dy[f2];
if ((!est[sx][sy])||(!est[tx][ty])) return;
std::queue<Que> que;
Que tmp={sx,sy,0};
que.push(tmp);
memset(vis,false,sizeof(vis));
vis[x][y]=vis[sx][sy]=true;
while(!que.empty()) {
tmp=que.front(),que.pop();
for (ri i(0);i<4;pd(i)) {
int kx=tmp.x+dx[i],ky=tmp.y+dy[i];
if (kx<1||kx>n||ky<1||ky>m) continue;
if (!vis[kx][ky]&&est[kx][ky]) {
vis[kx][ky]=true;
Que nw={kx,ky,tmp.d+1};
if (kx==tx&&ky==ty) {mv[x][y][f1][f2]=nw.d;return;}
que.push(nw);
}
}
}
};
auto init=[]() {
memset(mv,0x3f,sizeof(mv));
for (ri i(1);i<=n;pd(i))
for (ri j(1);j<=m;pd(j))
if (est[i][j])
for (ri k(0);k<4;pd(k))
for (ri l(0);l<4;pd(l))
if (l==k) mv[i][j][k][l]=0;
else bfs(i,j,k,l);
};
auto solve=[](int x,int y) {
cnt=0;
memset(vis,false,sizeof(vis));
vis[x][y]=vis[sx][sy]=true;
Que tmp={x,y,0};
std::queue<Que> que;
que.push(tmp);
while(!que.empty()) {
tmp=que.front(),que.pop();
for (ri i(0);i<4;pd(i)) {
int kx=tmp.x+dx[i],ky=tmp.y+dy[i];
if (kx<1||kx>n||ky<1||ky>m) continue;
if (est[kx][ky]&&!vis[kx][ky]) {
vis[kx][ky]=true;
que.push({kx,ky,tmp.d+1});
} else if (kx==sx&&ky==sy) qe[++cnt]={kx,ky,(i+2)%4},dis[kx][ky][(i+2)%4]=tmp.d;
}
}
};
auto spfa=[]() {
memset(vs,false,sizeof(vs));
std::queue<Que> que;
for (ri i(1);i<=cnt;pd(i)) que.push(qe[i]),vs[qe[i].x][qe[i].y][qe[i].d]=true;
Que tmp;
while(!que.empty()) {
tmp=que.front(),que.pop();
vs[tmp.x][tmp.y][tmp.d]=false;
for (ri i(0);i<4;pd(i)) {
int kx=tmp.x+dx[i],ky=tmp.y+dy[i],td;
if (kx<1||kx>n||ky<1||ky>m) continue;
if (dis[kx][ky][td=(i+2)%4]>dis[tmp.x][tmp.y][tmp.d]+mv[tmp.x][tmp.y][tmp.d][i]+1) {
dis[kx][ky][td]=dis[tmp.x][tmp.y][tmp.d]+mv[tmp.x][tmp.y][tmp.d][i]+1;
if (!vs[kx][ky][td]) {
vs[kx][ky][td]=true;
que.push({kx,ky,td});
}
}
}
}
};
inline int main() {
FI=freopen("y.in","r",stdin);
FO=freopen("y.out","w",stdout);
cin >> n >> m >> q;
for (ri i(1);i<=n;pd(i))
for (ri j(1);j<=m;pd(j)) cin >> est[i][j];
init();
for (ri z(1);z<=q;pd(z)) {
cin >> ex >> ey >> sx >> sy >> tx >> ty;
if (sx==tx&&sy==ty) printf("0
");
else {
memset(dis,0x3f,sizeof(dis));
solve(ex,ey);
spfa();
int ans=1061109567;
for (ri i(0);i<4;pd(i)) ans=cmin(ans,dis[tx][ty][i]);
printf("%d
",ans==1061109567?-1:ans);
}
}
return 0;
}
}
int main() {return nanfeng::main();}