Legend
Link ( extrm{to Luogu})。
题目描述就不搬了。
Editorial
显然，可以看做空位在一直移动，移动到目标棋子旁边就可以交换一下空位和目标棋子的位置，最后要让目标棋子到目标位置。
有一个非常显然的做法记录节点状态为：【空位坐标】+【目标棋子坐标】的形式。直接 0-1 bfs 就是 (O(Tn^2m^2)) 的，足够拿到 (60) 分。
想办法优化状态，有什么状态是无效的？显然，目标棋子会移动当且仅当空位在目标棋子相邻格子。
不难想到把节点状态改为：【目标棋子坐标】+【空位在目标棋子上下左右哪个方向】。这样状态数量就变成了 (4nm)。
那么如何转移状态？我们可以预处理一个 (dist) 数组 (dist[a][b][c][d][e][f])
表示空位初始在 ((a,b))，目标棋子在 ((c,d))，空位要走到 ((e,f)) 的最短路长度。
（在这里目标棋子没有什么用，仅仅看做一个障碍，空位不能移动到上面去）
这就有问题了：这样状态数不就又变成 (O(n^3m^3)) 了吗？
其实不然，我们发现由于上面已经进行了无效状态的去除，所以目标棋子一定会在初始空位的上下左右，这样状态数就又变成了 (4n^2m^2)。
预处理只要 bfs，复杂度与状态数相同，就是 (O(n^2m^2))。
还有唯一一个问题：最初的时候空位并不一定在目标棋子四周。所以我们要强行把它移动过去——但我们怎么知道移动过去的代价呢？
其实我们调用 (dist) 数组就可以了，由于转移是双向的，可以看做从目标棋子四周移动到初始位置。
接着我们用 Dijkstra 跑出答案就可以啦！复杂度是 (O(n^2m^2+Tnm log (nm)))
Code
使用这种方法要特判起点与终点相同的情况。
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)
freopen(#x".in" ,"r" ,stdin);
freopen(#x".out" ,"w" ,stdout)
#define LL long long
using namespace std;
const int MX = 32;
const LL MOD = 998244353;
const int INF = 0x3f3f3f3f;
int read(){
char k = getchar(); int x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
return x;
}
const int dx[] = {1 ,-1 ,0, 0};
const int dy[] = {0 ,0 ,-1 ,1};
int n ,m ,q;
bool ban[MX][MX];
int dis[MX][MX][4][MX][MX];
// 表示的是【空位】在 (x,y)，【出发点】位于【空位】的相对位置是 d
// 【空位】要走到 tx,ty 的最短路。
bool check(int x ,int y){
return !ban[x][y] && x >= 1 && x <= n && y >= 1 && y <= m;
}
bool getpos(int x ,int y ,int tx ,int ty){
// tx,ty 相对 x,y 的位置
for(int i = 0 ; i < 4 ; ++i){
if(dx[i] == tx - x && dy[i] == ty - y){
return i;
}
}
assert(0);
return -1;
}
void bfs(int tx ,int ty ,int dir){
memset(dis[tx][ty][dir] ,0x3f ,sizeof dis[0][0][0]);
int *dist[MX];
for(int i = 1 ; i <= n ; ++i)
dist[i] = dis[tx][ty][dir][i];
queue<int> X ,Y;
X.push(tx) ,Y.push(ty);
dist[tx][ty] = 0;
while(!X.empty()){
int x = X.front() ,y = Y.front();
X.pop() ,Y.pop();
for(int i = 0 ,tx ,ty ; i < 4 ; ++i){
tx = x + dx[i] ,ty = y + dy[i];
if(!check(tx ,ty) || dist[tx][ty] < INF) continue;
dist[tx][ty] = dist[x][y] + 1;
X.push(tx) ,Y.push(ty);
}
}
}
struct node{
int x ,y ,t;
int dist;
bool operator <(const node &B)const{
return dist > B.dist;
}
};
int dp[MX][MX][4] ,vis[MX][MX][4];
int dijkstra(int ex ,int ey ,int sx ,int sy ,int TX ,int TY){
memset(dp ,0x3f ,sizeof dp);
memset(vis ,0 ,sizeof vis);
if(sx == TX && sy == TY){
return 0;
}
std::priority_queue<node> q;
for(int i = 0 ,endx ,endy ; i < 4 ; ++i){
endx = sx + dx[i] ,endy = sy + dy[i];
if(!check(endx ,endy)) continue;
int dist = INF;
dist = std::min(dist ,dis[endx][endy][i ^ 1][ex][ey]);
if(dist < INF){
q.push((node){sx ,sy ,i ,dist});
// X.push(sx) ,Y.push(sy) ,D.push(i);
dp[sx][sy][i] = dist;
}
}
while(!q.empty()){
node tmp = q.top(); q.pop();
int x = tmp.x ,y = tmp.y ,d = tmp.t;
int nx = x + dx[d] ,ny = y + dy[d];
if(x == TX && y == TY)
return dp[x][y][d] < INF ? dp[x][y][d] : -1;
if(vis[x][y][d] || tmp.dist != dp[x][y][d]) continue;
vis[x][y][d] = 1;
if(dp[nx][ny][d ^ 1] > dp[x][y][d] + 1){
dp[nx][ny][d ^ 1] = dp[x][y][d] + 1;
q.push((node){nx ,ny ,d ^ 1 ,dp[x][y][d] + 1});
// X.push(nx) ,Y.push(ny) ,D.push(d ^ 1);
}
for(int i = 0 ; i < 4 ; ++i){
int tx = x + dx[i] ,ty = y + dy[i];
if(!check(tx ,ty)) continue;
int dist = dis[nx][ny][d ^ 1][tx][ty];
if(dp[x][y][i] > dp[x][y][d] + dist){
dp[x][y][i] = dp[x][y][d] + dist;
q.push((node){x ,y ,i ,dp[x][y][d] + dist});
// X.push(x) ,Y.push(y) ,D.push(i);
}
}
}
return -1;
}
void solve(){
n = read() ,m = read() ,q = read();
for(int i = 1 ; i <= n ; ++i){
for(int j = 1 ; j <= m ; ++j){
ban[i][j] = !read();
}
}
for(int i = 1 ; i <= n ; ++i){
for(int j = 1 ; j <= m ; ++j){
if(ban[i][j]) continue;
for(int d = 0 ,tx ,ty ; d < 4 ; ++d){
tx = i + dx[d] ,ty = j + dy[d];
if(!check(tx ,ty)){
continue;
}
ban[tx][ty] ^= 1;
bfs(i ,j ,d);
ban[tx][ty] ^= 1;
}
}
}
while(q--){
int ex ,ey ,sx ,sy ,tx ,ty;
ex = read() ,ey = read();
sx = read() ,sy = read();
tx = read() ,ty = read();
printf("%d
" ,dijkstra(ex ,ey ,sx ,sy ,tx ,ty));
}
}
int main(){
int T = 1;
for(int i = 1 ; i <= T ; ++i){
solve();
}
return 0;
}