题目大意

一个 $n\times m$ 的棋盘上填充着棋子，其中有一个空格。除了一些固定的棋子，空格相邻的棋子可以移动到空格上。一个棋盘上固定的棋子是确定的，给出 $q$ 个询问，对于每个询问回答，空格一开始在 $(ex,ey)$ 时， $(sx,sy)$ 上的指定棋子能否移动到 $(tx,ty)$ 和最少操作数。

$n,m\le30,q\le500$ .

思路

优先考虑初始位置就是目的地的特殊情况，操作数为零。再考虑通常情况，不难从“其实是空格在移动”的方向思考。

指定棋子到目的地的操作示例如图：

不难发现，路径其实分为两段：

1. 空格移动到与指定棋子相邻处。若没有空格相邻，棋子肯定动不了，所以第一阶段必然是空格靠近指定棋子；
2. 指定棋子与空格一起移动到目的地。由图，它们移动的方式是类似转着圈移动。

对于第一段，由于空格和指定棋子都不确定，每次询问时 BFS 即可。

对于第二段，它们运动的轨迹较为复杂，加之以固定棋子为障碍，或许不好直接“呆板的暴力”。注意到，两者的“一大步”是指定棋子替代空格的位置后，空格再找到合适的相邻处，这“一大步”的操作对于棋盘来说是确定的（可以预处理）。

以此为基础，我们以这“一大步”作为边，两者的位置一并看作点，“一大步”所需操作数为边权建立图论模型。这样，最短路即为第二段的答案。

复杂度 $\mathcal{O}(n^2m^2+qnm\log nm)$ 。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 40, mod = 998244353, inf = 1010580540;

inline ll read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

inline int add (int a, int b) { return a + b > mod? a + b - mod: a + b; }
inline int dec (int a, int b) { return a < b? a - b + mod: a - b; }
inline int mul (int a, int b) { return 1ll * a * b % mod; }

namespace Main {	
	int n, m;
	bool a[N][N];

	int rots[2][4] = {{0, 1, -1, 0}, {1, 0, 0, -1}};
	bool border(int x, int y) { return 1 <= x && x <= n && 1 <= y && y <= m; }
	bool able(int x, int y) { return border(x, y) && a[x][y]; }

	int head[N * N * 4], etot;
	struct edge { int to, nxt, w; } e[N * N * 32];
	void add(int u, int v, int w) { e[++etot] = (edge){v, head[u], w}, head[u] = etot; }
	struct node { int x, y, rot; };
	int id[N][N][4];

	int dis[N][N];
	bool vis[N][N];
	void bfs(int ix, int iy) {
		queue<node> q;
		q.push({ix, iy, -1});
		memset(vis, 0, sizeof vis);
		vis[ix][iy] = 1;
		while (!q.empty()) {
			node u = q.front(); q.pop();
			for (int rot = 0; rot < 4; ++rot) {
				int x = u.x + rots[0][rot], y = u.y + rots[1][rot];
				if (able(x, y) && dis[x][y] > dis[u.x][u.y] + 1) {
					dis[x][y] = dis[u.x][u.y] + 1;
					if (vis[x][y]) continue; vis[x][y] = 1;
					q.push({x, y, -1});
				}
			}
			vis[u.x][u.y] = 0;
		}
	}

	void prework() {
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j)
				if (able(i, j))
					for (int rot = 0; rot < 4; ++rot) {
						int x = i + rots[0][rot], y = j + rots[1][rot];
						if (able(x, y)) {
							int u = (id[i][j][rot]? id[i][j][rot]: (id[i][j][rot] = ++etot));
							a[x][y] = 0;
							memset(dis, 60, sizeof dis);
							dis[i][j] = 1;
							// printf ("DEBUG P=(%d,%d)\n", i,j);
							bfs(i, j);
							for (int rot2 = 0; rot2 < 4; ++rot2) {
								int nx = x + rots[0][rot2], ny = y + rots[1][rot2];
								if (border(nx, ny) && dis[nx][ny] <= inf) {
									int v = (id[x][y][rot2]? id[x][y][rot2]: (id[x][y][rot2] = ++etot));
									add(u, v, dis[nx][ny]);
								}
							}
							a[x][y] = 1;
						}
					}
	}

	bool vs[N * N * 4];
	int dt[N * N * 4];
	void spfa(int x, int y) {
		queue<int>q;
		memset(vs, 0, sizeof vs);
		memset(dt, 60, sizeof(int) * (etot + 5));
		
		for (int rot = 0, u; rot < 4; ++rot)
			if (u = id[x][y][rot]) {
				q.push(u);
				dt[u] = dis[x + rots[0][rot]][y + rots[1][rot]];
				vs[u] = 1;
			}

		while(!q.empty()) {
			int u = q.front(); q.pop();
			for (int i = head[u]; i; i = e[i].nxt) {
				int v = e[i].to;
				if (!(dt[v] > dt[u] + e[i].w)) continue;
				dt[v] = dt[u] + e[i].w;
				q.push(v);
			}
			vs[u] = 0;
		}
	}

	int main () {
		n = read(), m = read(); int T = read();
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j) a[i][j] = read();

		// puts("DEBUG #1");
		prework();
		// puts("DEBUG #2");

		for (; T--; ) {
			int ex = read(), ey = read(), sx = read(), sy = read(), tx = read(), ty = read();
			
			if (sx == tx && sy == ty) { puts("0"); continue;}

			a[sx][sy] = 0;
			memset (dis, 60, sizeof dis);
			dis[ex][ey] = 0;
			bfs(ex, ey);
			a[sx][sy] = 1;

			spfa(sx, sy);

			int ans = inf;
			for (int rot = 0; rot < 4; ++rot) ans = min(ans, dt[id[tx][ty][rot]]);
			printf ("%d\n", (ans == inf? -1: ans));
		}
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}