Description：

一个 $n \times m$ 棋盘有一个格子是空的，其余 $n \times m-1$ 个格子上每个格子上有一个棋子，有些棋子是固定的，有些棋子则是可以移动的；对于同样的一个棋盘， $q$ 给定起点、终点和空格子的位置，求把在起点的特殊棋子从起点移到终点的最少操作次数。

$1\le n,m\le 30,1\le q \le 500$

Solution：

一个显然的思路是直接 $BFS$ 可以获得 $70$ 分，然而每次棋盘是相同的，多次 $BFS$ 显然存在大量冗余。

挖掘一下这道题本身的性质，会发现最终棋子的走向一定是空白格一步步走向特殊棋子，然后空白格就没有离开过特殊棋子周围的 $8$ 个格子，先考虑后半部分，发现只有特殊棋子周围的四个位置才是有用的，棋子走到角上下一步也一定会回到周围的四个位置，所以他的状态量实际是 $O(nm)$ 的，这时棋子只有两种走法，从周围四个格子中的一个走到另一个，或者和特殊格子交换位置，第二种当然很好说，状态间连边权为 $1$ 的有向边，第一种的话，就要在询问前预处理每个格子从四周的一个位置走到另一个位置的步数，这个直接 $BFS$ 就好了。

这时候我们如果能让空白格子走到特殊格子周围，那么就可以跑 $SPFA$ 了，而这一步也可以直接 $BFS$ 实现。

然后原点向起始状态连对应距离的边，结束状态向终点连边权为 $0$ 的边，然后就是 $SPFA$ 了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m,q;

#define MAXN 32

#define INF 0x3f3f3f3f

int a[MAXN][MAXN];

int ex,ey,sx,sy,tx,ty;

int to(int i,int j,int k){return ((i - 1) * m + j) * 4 + k;}

int mx[4] = {0,0,1,-1};

int my[4] = {1,-1,0,0};

#define INF 0x3f3f3f3f

struct edge

{

	int to,nxt,v;

}e[MAXN * MAXN * 12];

int edgenum = 0;

int lin[MAXN * MAXN * 4] = {0};

void add(int a,int b,int c)

{//cout << a << " " << b << " " << c << endl;

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int dis[MAXN][MAXN];

#define fi first

#define se second

void BFS1(int x,int y,int d)

{

	a[x][y] = 0;

	memset(dis,-1,sizeof(dis));dis[x + mx[d]][y + my[d]] = 0;

	queue< pair<int,int> > q;q.push(make_pair(x + mx[d],y + my[d]));

	while(!q.empty())

	{

		pair<int,int> k = q.front();q.pop();

		for(int i = 0;i < 4;++i)

		{

			if(a[k.fi + mx[i]][k.se + my[i]] && dis[k.fi + mx[i]][k.se + my[i]] == -1)

			{

				dis[k.fi + mx[i]][k.se + my[i]] = dis[k.fi][k.se] + 1;

				q.push(make_pair(k.fi + mx[i],k.se + my[i]));

			}

		}

	}

	for(int k = 0;k < 4;++k)

		if(k != d && dis[x + mx[k]][y + my[k]] != -1)

			add(to(x,y,d),to(x,y,k),dis[x + mx[k]][y + my[k]]);

	if(a[x + mx[d]][y + my[d]])add(to(x,y,d),to(x + mx[d],y + my[d],d ^ 1),1);

	a[x][y] = 1;

	return;

}

int st,en;

void BFS2(int ex,int ey,int sx,int sy)

{

	a[sx][sy] = 0;

	memset(dis,-1,sizeof(dis));dis[ex][ey] = 0;

	queue< pair<int,int> > q;q.push(make_pair(ex,ey));

	while(!q.empty())

	{

		pair<int,int> k = q.front();q.pop();

		for(int i = 0;i < 4;++i)

		{

			if(a[k.fi + mx[i]][k.se + my[i]] && dis[k.fi + mx[i]][k.se + my[i]] == -1)

			{

				dis[k.fi + mx[i]][k.se + my[i]] = dis[k.fi][k.se] + 1;

				q.push(make_pair(k.fi + mx[i],k.se + my[i]));

			}

		}

	}

	for(int i = 0;i < 4;++i)

		if(a[sx + mx[i]][sy + my[i]] && dis[sx + mx[i]][sy + my[i]] != -1)

			add(st,to(sx,sy,i),dis[sx + mx[i]][sy + my[i]]);

	a[sx][sy] = 1;

	return;

}

int d[MAXN * MAXN * 4];

bool v[MAXN * MAXN * 4];

void SPFA()

{

	memset(d,0x3f,sizeof(d));d[st] = 0;

	queue<int> q;q.push(st);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		v[k] = false;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{

				d[e[i].to] = d[k] + e[i].v;

				if(!v[e[i].to])

				{

					v[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}

	return;

}

int cur[MAXN * MAXN * 4];

int main()

{

	scanf("%d%d%d",&n,&m,&q);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			scanf("%d",&a[i][j]);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			if(a[i][j])

				for(int k = 0;k < 4;++k)

					if(a[i + mx[k]][j + my[k]])BFS1(i,j,k);

	st = n * m * 4 + 4;en = st + 1;

	int top = edgenum;

	memcpy(cur,lin,sizeof(lin));

	for(int i = 1;i <= q;++i)

	{

		edgenum = top;

		memcpy(lin,cur,sizeof(lin));

		scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);

		if(sx == tx && sy == ty)

		{

			puts("0");

			continue;

		}

		BFS2(ex,ey,sx,sy);

		for(int k = 0;k < 4;++k)if(a[tx + mx[k]][ty + my[k]])add(to(tx,ty,k),en,0);

		SPFA();

		if(d[en] == INF)puts("-1");

		else printf("%d\n",d[en]);

	}

	return 0;

}