传送门
problem
数据范围：
1
≤
n
,
m
≤
30
1\le n,m\le 30
1≤n,m≤30，
q
≤
500
q\le 500
q≤500。
solution
这道题在 loj 上跑暴力有
80
80
80 分。。
暴力的思路就是记状态 [x,y,Sx,Sy] 表示当前空白格在 (x,y)，目标格在 (Sx,Sy) 的最短距离。枚举下一步走法更新答案即可。
冷静分析一下发现复杂度是
O
(
n
4
q
)
O(n^4q)
O(n4q) 的。代码在这里。
正解参考博客。正解的思想就很妙了，相当于是把有用状态记下来，在状态间进行连边表示转移，然后跑最短路。
首先考虑有用状态，发现只有空格放在目标格的上
/
/
/下
/
/
/左
/
/
/右时才是有用状态，记一下。
现在考虑状态之间的转移，对于一个目标格，有下面的转移：
空格围着目标格转。比如空格从目标格的上方移到右边，注意目标格是不动的。可以
b
f
s
bfs
bfs 求出最少移动次数。空格和目标格交换位置。这个很简单，连一条
1
1
1 的边即可。
有一个细节就是，一开始空格可能不在目标格的四周，我们还有一次
b
f
s
bfs
bfs 把空格移到它的四周去。
这种做法的意思就是，我们想求出从初始状态
S
S
S 转移到终点状态
T
T
T 的最少次数，不妨把所有状态间的转移连成边，边权是转移次数，那么最后的答案就是从
S
S
S 到
T
T
T 的一条路径，这就转化成了最短路的模型。
最后跑个 spfa 求最短路即可。
code
#include<bits/stdc++.h>
using namespace std
;
namespace IO
{
const int Rlen
=1<<22|1;
char buf
[Rlen
],*p1
,*p2
;
inline char gc(){
return (p1
==p2
)&&(p2
=(p1
=buf
)+fread(buf
,1,Rlen
,stdin),p1
==p2
)?EOF:*p1
++;
}
template<typename T
>
inline T
Read(){
char c
=gc();T x
=0,f
=1;
while(!isdigit(c
)) f
^=(c
=='-'),c
=gc();
while( isdigit(c
)) x
=(x
+(x
<<2)<<1)+(c
^48),c
=gc();
return f
?x
:-x
;
}
inline int in() {return Read
<int>();}
}
using IO
::in
;
const int N
=35,M
=2e4+5;
int n
,m
,q
,Ex
,Ey
,Sx
,Sy
,Tx
,Ty
,a
[N
][N
],f
[N
][N
];
int dx
[5]={-1,0,1,0};
int dy
[5]={0,1,0,-1};
int t
,first
[M
],v
[M
],w
[M
],nxt
[M
];
void add(int x
,int y
,int z
) {nxt
[++t
]=first
[x
],first
[x
]=t
,v
[t
]=y
,w
[t
]=z
;}
int id(int x
,int y
) {return ((x
-1)*m
+y
-1)<<2;}
typedef pair
<int,int> pii
;
queue
<pii
>Q
;
void bfs(int Ex
,int Ey
,int Sx
,int Sy
,int type
){
memset(f
,-1,sizeof(f
));
f
[Ex
][Ey
]=0,f
[Sx
][Sy
]=1;
Q
.push(pii(Ex
,Ey
));
while(!Q
.empty()){
pii now
=Q
.front();Q
.pop();
int x
=now
.first
,y
=now
.second
;
for(int i
=0;i
<4;++i
){
int X
=x
+dx
[i
],Y
=y
+dy
[i
];
if(X
>=1&&X
<=n
&&Y
>=1&&Y
<=m
&&a
[X
][Y
]&&f
[X
][Y
]==-1) f
[X
][Y
]=f
[x
][y
]+1,Q
.push(pii(X
,Y
));
}
}
if(type
==4) return;
int tmp
=id(Sx
,Sy
);
for(int i
=0;i
<4;++i
){
int x
=Sx
+dx
[i
],y
=Sy
+dy
[i
];
if(f
[x
][y
]>0) add(tmp
+type
,tmp
+i
,f
[x
][y
]);
}
add(tmp
+type
,id(Ex
,Ey
)+(type
+2)%4,1);
}
int d
[M
],vis
[M
],inf
;
void spfa(int Sx
,int Sy
){
queue
<int>Q
;
memset(vis
,0,sizeof(vis
));
memset(d
,127/3,sizeof(d
));
inf
=d
[0];
for(int i
=0;i
<4;++i
){
int x
=Sx
+dx
[i
],y
=Sy
+dy
[i
];
if(x
>=1&&x
<=n
&&y
>=1&&y
<=m
&&f
[x
][y
]!=-1){
int sta
=id(Sx
,Sy
)+i
;
d
[sta
]=f
[x
][y
],Q
.push(sta
);
}
}
while(!Q
.empty()){
int x
=Q
.front();Q
.pop();
vis
[x
]=0;
for(int i
=first
[x
];i
;i
=nxt
[i
]){
int to
=v
[i
];
if(d
[to
]>d
[x
]+w
[i
]){
d
[to
]=d
[x
]+w
[i
];
if(!vis
[to
]) vis
[to
]=1,Q
.push(to
);
}
}
}
}
int main(){
n
=in(),m
=in(),q
=in();
for(int i
=1;i
<=n
;++i
)
for(int j
=1;j
<=m
;++j
) a
[i
][j
]=in();
for(int i
=1;i
<=n
;++i
){
for(int j
=1;j
<=m
;++j
) if(a
[i
][j
]){
if(a
[i
-1][j
]) bfs(i
-1,j
,i
,j
,0);
if(a
[i
][j
+1]) bfs(i
,j
+1,i
,j
,1);
if(a
[i
+1][j
]) bfs(i
+1,j
,i
,j
,2);
if(a
[i
][j
-1]) bfs(i
,j
-1,i
,j
,3);
}
}
while(q
--){
Ex
=in(),Ey
=in(),Sx
=in(),Sy
=in(),Tx
=in(),Ty
=in();
if(Sx
==Tx
&&Sy
==Ty
) {puts("0");continue;}
bfs(Ex
,Ey
,Sx
,Sy
,4),spfa(Sx
,Sy
);
int ans
=inf
;
for(int j
=0;j
<4;++j
) ans
=min(ans
,d
[id(Tx
,Ty
)+j
]);
printf("%d\n",(ans
==inf
)?-1:ans
);
}
return 0;
}
