#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define inf 0x3f3f3f3f
#define N 35
#define maxn 5000
#define mod 1000000007
#define ll long long
using namespace std; int n,m,q,cte;
int ok[N][N],id[N][N],head[maxn],dis[maxn],inq[maxn],st[];
int xx[]={-,,,};
int yy[]={,,,-};
struct EDGE{
int to,nxt,val;
}edge[maxn*];
struct node{
int x,y;
};
node ins(int s1,int s2) {node k;k.x=s1;k.y=s2;return k;}
bool check(int x,int y)
{
if(x<||y<||x>n||y>m||!ok[x][y]) return false;
else return true;
}
void edge_add(int u,int v,int w)
{
cte++;
edge[cte].to = v;
edge[cte].nxt=head[u];
edge[cte].val= w;
head[u]=cte;
}
void bfs(int ex,int ey,int sx,int sy,int d)
{
queue<node>q;
memset(dis,-,sizeof(dis));
dis[id[ex][ey]]=,dis[id[sx][sy]]=;
q.push(ins(ex,ey));
int x,y,fx,fy;
while(!q.empty())
{
node k=q.front();q.pop();
x=k.x,y=k.y;
for(int i=;i<;i++)
{
fx=x+xx[i],fy=y+yy[i];
if(!check(fx,fy)||dis[id[fx][fy]]!=-) continue;
dis[id[fx][fy]]=dis[id[x][y]]+;
q.push(ins(fx,fy));
}
}
for(int i=;i<;i++)
{
fx=sx+xx[i],fy=sy+yy[i];
if(!check(fx,fy)||dis[id[fx][fy]]==-||i==d) continue;
edge_add(id[sx][sy]+d,id[sx][sy]+i,dis[id[fx][fy]]);
}
edge_add(id[sx][sy]+d,id[ex][ey]+(d+)%,);
}
void bfsS(int ex,int ey,int sx,int sy)
{
queue<node>q;
memset(dis,-,sizeof(dis));
q.push(ins(ex,ey)),dis[id[ex][ey]]=;
int x,y,fx,fy;
while(!q.empty())
{
node k=q.front();q.pop();
x=k.x,y=k.y;
for(int i=;i<;i++)
{
fx=x+xx[i],fy=y+yy[i];
if(!check(fx,fy)||dis[id[fx][fy]]!=-||(fx==sx&&fy==sy)) continue;
dis[id[fx][fy]]=dis[id[x][y]]+;
q.push(ins(fx,fy));
}
}
}
void build_edge()
{
int ct=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(ok[i][j]) id[i][j]=ct,ct+=;
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(!check(i,j)) continue;
if(check(i-,j)) bfs(i-,j,i,j,);
if(check(i,j+)) bfs(i,j+,i,j,);
if(check(i+,j)) bfs(i+,j,i,j,);
if(check(i,j-)) bfs(i,j-,i,j,);
}
}
void spfa(int S)
{
queue<int>q;
memset(dis,0x3f,sizeof(dis));
q.push(S),dis[S]=,inq[S]=;
while(!q.empty())
{
int u=q.front();q.pop();
for(int j=head[u];j!=-;j=edge[j].nxt)
{
int v=edge[j].to;
if(dis[v]>dis[u]+edge[j].val)
{
dis[v]=dis[u]+edge[j].val;
if(!inq[v]) q.push(v),inq[v]=;
}
}
inq[u]=;
}
} int solve(int ex,int ey,int sx,int sy,int tx,int ty)
{
bfsS(ex,ey,sx,sy);
if(sx==tx&&sy==ty) return ;
for(int i=;i<;i++) st[i]=dis[id[sx+xx[i]][sy+yy[i]]];
int fx,fy,ans=inf;
for(int i=;i<;i++)
{
fx=sx+xx[i],fy=sy+yy[i];
if(!check(fx,fy)||st[i]==-) continue;
spfa(id[sx][sy]+i);
for(int j=;j<;j++)
{
if(!check(tx+xx[j],ty+yy[j])||dis[id[tx][ty]+j]==-) continue;
ans=min(ans,st[i]+dis[id[tx][ty]+j]);
}
}
if(ans>=inf) return -;
else return ans;
} int main()
{
freopen("aa.in","r",stdin);
scanf("%d%d%d",&n,&m,&q);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&ok[i][j]);
memset(head,-,sizeof(head));
build_edge();
int ex,ey,sx,sy,tx,ty;
while(q--)
{
scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
printf("%d\n",solve(ex,ey,sx,sy,tx,ty));
}
return ;
}
---恢复内容开始---
题目大意：类似于华容道游戏，但所有棋子都是11大小的，棋盘上仅有一个空格，其它位置填满了棋子，有些棋子是固定的不能被移动，每个格子内只能有一个棋子，棋子只能移动到相邻的空格上，每移动任意棋子一次视为一次操作，求让指定棋子移动到指定位置的最小操作数
据说爆搜能拿70pts....
观察爆搜为什么会T，主要是因为搜出了许多无用的状态
考虑优化这个过程，空格在指定棋子的上下左右分别记为一种状态，相当于一个位置记录了4个状态
为了方便转移，直接把每个格子的四个状态记成连续的，这样方便转移
每种状态，它能转移到其它状态的情况分为两种：
<1>指定格子的某个方向有空格，转移到同一个格子的另一个方向有空格，指定格子上的棋子的位置不动
这种情况，我们对于每个格子的四个方向分别bfs即可，因为除了空格子，其它位置都被填满了，所以空格子在被填满的棋盘里移动，和棋子在空棋盘里的移动方式是一样的（貌似是一句废话但我仍然思考了很久...）
<2>指定棋子朝着这个状态指向的空格移动
这种情况，显然操作次数为1，转移的状态呢，则是从 当前格子的指向 转移到 目标格子的反方向 (就是那个(d+2)%4)
虽然有500次询问，但图都是一样的，所以建一次图就行
那么，如果一开始空格子不在指定棋子边上呢？
我们把空格子移动到指定棋子的四个方向就行了，注意不要让空格子移动到指定棋子的格子上
再分别跑一次SPFA最短路即可
总结：之前还有一道棋盘建图题（荷叶塘），但那道题建图更简单更好想，思路都是先bfs建边，然后跑最短路
注意特判移动次数为0的情况！
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define inf 0x3f3f3f3f
#define N 35
#define maxn 5000
#define mod 1000000007
#define ll long long
using namespace std; int n,m,q,cte;
int ok[N][N],id[N][N],head[maxn],dis[maxn],inq[maxn],st[];
int xx[]={-,,,};
int yy[]={,,,-};
struct EDGE{
int to,nxt,val;
}edge[maxn*];
struct node{
int x,y;
};
node ins(int s1,int s2) {node k;k.x=s1;k.y=s2;return k;}
bool check(int x,int y)
{
if(x<||y<||x>n||y>m||!ok[x][y]) return false;
else return true;
}
void edge_add(int u,int v,int w)
{
cte++;
edge[cte].to = v;
edge[cte].nxt=head[u];
edge[cte].val= w;
head[u]=cte;
}
void bfs(int ex,int ey,int sx,int sy,int d)
{
queue<node>q;
memset(dis,-,sizeof(dis));
dis[id[ex][ey]]=,dis[id[sx][sy]]=;
q.push(ins(ex,ey));
int x,y,fx,fy;
while(!q.empty())
{
node k=q.front();q.pop();
x=k.x,y=k.y;
for(int i=;i<;i++)
{
fx=x+xx[i],fy=y+yy[i];
if(!check(fx,fy)||dis[id[fx][fy]]!=-) continue;
dis[id[fx][fy]]=dis[id[x][y]]+;
q.push(ins(fx,fy));
}
}
for(int i=;i<;i++)
{
fx=sx+xx[i],fy=sy+yy[i];
if(!check(fx,fy)||dis[id[fx][fy]]==-||i==d) continue;
edge_add(id[sx][sy]+d,id[sx][sy]+i,dis[id[fx][fy]]);
}
edge_add(id[sx][sy]+d,id[ex][ey]+(d+)%,);
}
void bfsS(int ex,int ey,int sx,int sy)
{
queue<node>q;
memset(dis,-,sizeof(dis));
q.push(ins(ex,ey)),dis[id[ex][ey]]=;
int x,y,fx,fy;
while(!q.empty())
{
node k=q.front();q.pop();
x=k.x,y=k.y;
for(int i=;i<;i++)
{
fx=x+xx[i],fy=y+yy[i];
if(!check(fx,fy)||dis[id[fx][fy]]!=-||(fx==sx&&fy==sy)) continue;
dis[id[fx][fy]]=dis[id[x][y]]+;
q.push(ins(fx,fy));
}
}
}
void build_edge()
{
int ct=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(ok[i][j]) id[i][j]=ct,ct+=;
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(!check(i,j)) continue;
if(check(i-,j)) bfs(i-,j,i,j,);
if(check(i,j+)) bfs(i,j+,i,j,);
if(check(i+,j)) bfs(i+,j,i,j,);
if(check(i,j-)) bfs(i,j-,i,j,);
}
}
void spfa(int S)
{
queue<int>q;
memset(dis,0x3f,sizeof(dis));
q.push(S),dis[S]=,inq[S]=;
while(!q.empty())
{
int u=q.front();q.pop();
for(int j=head[u];j!=-;j=edge[j].nxt)
{
int v=edge[j].to;
if(dis[v]>dis[u]+edge[j].val)
{
dis[v]=dis[u]+edge[j].val;
if(!inq[v]) q.push(v),inq[v]=;
}
}
inq[u]=;
}
} int solve(int ex,int ey,int sx,int sy,int tx,int ty)
{
bfsS(ex,ey,sx,sy);
if(sx==tx&&sy==ty) return ;
for(int i=;i<;i++) st[i]=dis[id[sx+xx[i]][sy+yy[i]]];
int fx,fy,ans=inf;
for(int i=;i<;i++)
{
fx=sx+xx[i],fy=sy+yy[i];
if(!check(fx,fy)||st[i]==-) continue;
spfa(id[sx][sy]+i);
for(int j=;j<;j++)
{
if(!check(tx+xx[j],ty+yy[j])||dis[id[tx][ty]+j]==-) continue;
ans=min(ans,st[i]+dis[id[tx][ty]+j]);
}
}
if(ans>=inf) return -;
else return ans;
} int main()
{
freopen("aa.in","r",stdin);
scanf("%d%d%d",&n,&m,&q);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&ok[i][j]);
memset(head,-,sizeof(head));
build_edge();
int ex,ey,sx,sy,tx,ty;
while(q--)
{
scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
printf("%d\n",solve(ex,ey,sx,sy,tx,ty));
}
return ;
}
---恢复内容结束---