初步想法
由题，我们可以想出一种显然的宽搜算法。
我们可以使用四元组$(ex,ey,x,y)$唯一表示题目的状态。
$(ex,ey)$表示空格所在坐标
$(x,y)$表示点所在坐标
那么我们就可以得到$O(q(n\times m)^2)$的搜索算法。
算法优化
显然，上述的时间复杂度是无法通过$100\%$的数据的。
我们需要对四元组的状态进行压缩：
由题目的移动方式我们可以发现，只有空格在点的周围才能够移动点，也就是说在有效的转移中，空格在点的周围。
有了以上性质，我们就可以将四元组替换为三元组：
$(x,y,d)$表示点在$(x,y)$，空格在其$d$方向上，$d\in[0,4)$
因此我们可以设状态$f[x,y,d]$表示点从起始点走到$(x,y)$，空格在其$d$方向上所需代价。
如图，想要将$(x,y)$转移到$(nx,ny)$需要先将空格移动到$(nx,ny)$。
因此我们还需要一个数组$dist[sx,sy,x,y,d]$表示空格在$(sx,sy)$的$d$方向上走到$(x,y)$的位置所需代价。
那么我们可以通过$O(4(n\times m)^2)$的代价预处理出$dist[]$
具体方法是枚举$(sx,sy)$和$d$，用一次简单的Bfs预处理出另外两维。
注意$dist[]$数组转移时不能到达$(sx,sy)$点，否则有误，正确性证明见后面。
那么我们就可以表示$f[]$的转移了。
如图
第三维$(nd+2)\%4$是因为沿着$nd$方向转移后，空格在其反方向，需要在方向数组中处理一下。
$f$数组初始化：
其中$(sx,sy)$是初始点坐标，$(Ex,Ey)$是初始空格坐标。
然后统计答案：
正确性证明
若不规定$(sx,sy)$不能到达，正确性显然。
$f[]$转移时显然不能经过中间点。
但是$f[]$初始化时将空格移动到起始点周围似乎是可以经过起始点的。
那么如果可以经过$(sx,sy)$，可能引起非最优的情况如下图：
如图，Start的位置改变了，但是我们的程序并不会判断到上述情况。
真的不会吗？我们发现上述情况和下图是等价的。
Spfa再进行一次交换，代价和上述情况相同。
故正确性得到证明。
小优化
我们发现其实$dist[]$充当$f[]$的转移媒介，因此我们根本不需要五维，四维就够了。
$dist[x,y,d1,d2]$表示空格在$(x,y)$的$d1$方向上，空格要移动到$d2$方向上去所需的代价。
同样可以对$dist[]$ Bfs预处理。
缺点：
对Spfa的$f[]$的初始化需要重新Bfs 4次。
而且细节比较多。
代码
代码实现的是没有经过优化的算法。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int Dirx[]= {1,0,-1,0},Diry[]= {0,1,0,-1};
struct Point {
int x,y;
} Empty,Start,End;
int n,m,q,dist[35][35][35][35][4],vst[35][35],map[35][35],f[35][35][4],inque[35][35][4];
void Bfs(int sx,int sy,int d) {
queue<Point>Q;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
dist[sx][sy][i][j][d]=0x7fffffff/2;
memset(vst,0,sizeof(vst));
int x=sx+Dirx[d],y=sy+Diry[d];
if(x<1||x>n||y<1||y>m||map[x][y]==0)return;
dist[sx][sy][x][y][d]=0;
Q.push((Point) {
x,y
});
vst[x][y]=vst[sx][sy]=1; //不能走sx,sy可以证明正确性
while(!Q.empty()) {
Point Now=Q.front();
Q.pop();
for(int i=0; i<4; i++) {
Point Next= {Now.x+Dirx[i],Now.y+Diry[i]};
if(Next.x<1||Next.x>n||Next.y<1||Next.y>m||map[Next.x][Next.y]==0||vst[Next.x][Next.y])continue;
Q.push(Next);
vst[Next.x][Next.y]=1;
dist[sx][sy][Next.x][Next.y][d]=dist[sx][sy][Now.x][Now.y][d]+1;
}
}
}
struct QueNode {
int x,y,d;
};
void Spfa() {
queue<QueNode>Q;
memset(f,0x3f,sizeof(f));
for(int d=0; d<4; d++) {
Point Next= {Start.x+Dirx[d],Start.y+Diry[d]};
if(Next.x<1||Next.x>n||Next.y<1||Next.y>m||map[Next.x][Next.y]==0)continue;
f[Start.x][Start.y][d]=dist[Start.x][Start.y][Empty.x][Empty.y][d];
Q.push((QueNode) {
Start.x,Start.y,d
});
}
while(!Q.empty()) {
QueNode Now=Q.front();
Q.pop();
inque[Now.x][Now.y][Now.d]=0;
for(int i=0; i<4; i++) {
Point Next= {Now.x+Dirx[i],Now.y+Diry[i]};
if(Next.x<1||Next.x>n||Next.y<1||Next.y>m||map[Next.x][Next.y]==0)continue;
if(f[Next.x][Next.y][(i+2)%4]>f[Now.x][Now.y][Now.d]+dist[Now.x][Now.y][Next.x][Next.y][Now.d]+1) {
f[Next.x][Next.y][(i+2)%4]=f[Now.x][Now.y][Now.d]+dist[Now.x][Now.y][Next.x][Next.y][Now.d]+1;
if(!inque[Next.x][Next.y][(i+2)%4]) {
inque[Next.x][Next.y][(i+2)%4]=1;
Q.push((QueNode) {
Next.x,Next.y,(i+2)%4
});
}
}
}
}
}
int main() {
n=Get_Int();
m=Get_Int();
q=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
map[i][j]=Get_Int();
for(int sx=1; sx<=n; sx++)
for(int sy=1; sy<=m; sy++)
for(int d=0; d<4; d++)
Bfs(sx,sy,d);
for(int i=1; i<=q; i++) {
Empty.x=Get_Int();
Empty.y=Get_Int();
Start.x=Get_Int();
Start.y=Get_Int();
End.x=Get_Int();
End.y=Get_Int();
if(Start.x==End.x&&Start.y==End.y) {
puts("0");
continue;
}
Spfa();
int ans=0x7fffffff/2;
for(int d=0; d<4; d++)ans=min(ans,f[End.x][End.y][d]);
if(ans>=0x3f3f3f3f)puts("-1");
else printf("%d\n",ans);
}
return 0;
}
