标题粗心

具体标题传送门

\(n\times m\) 的华容道盘，有妨碍。多组问询，每组妨碍不变。其间要将初始在 \((sx,sy)\) 的棋子移动到 \((tx,ty)\)。初始空白的方位在 \((ex,ey)\)。求至少多少次移动完结方针，无法完结输出 -1。

\(n,m\leq30,q\leq 500\)。

思路

发现明显应该是要预处理什么东西然后关于每组问询再做。然后发现其实这个游戏便是用空格铺路让棋子依照合法的最短间隔一步一步走。

手玩一下能够发现先依照最短间隔将空格移动到初始方位之后就能够开端移动了。发现假如要移动一个棋子到一个方向就需要在不移动原棋子的情况下移动空格。

之后就能够写一个移动的函数了，用宽搜 \(f(cx,cy,sx,sy,ex,ey)\) 表明空格一开端在 \((sx,sy)\)，在不经过 \((cx,cy)\) 时移动到 \((ex,ey)\) 的最短步数。

可是假如咱们预处理出一切的 \(f\) 就能够以它为边权跑最短路就能够了。可是发现预处理的时刻复杂度是 \(O(n^8)\) 的，无法承受。

观察到其实每一次的移动除了一开端移动空格到起点四周外只会在四个方向动。所以经过跑 \(f()\) 来算新的 \(v(x,y,a,b)\)，其间 \(a,b\in[0,4)\) 表明四个方向。这样咱们能够经过 \(T(16n^4)\) 的办法求助这个棋盘移动恣意一个方位的步数。

发现关于每一组问询跑最短路即可。可是关于状况我设置的与一般最短路略有不同，设了 \(d(x,y,a),a\in[0,4)\) 表明现在在 \((x,y)\)，空格在 \((x,y)\) 的 \(a\) 方向时的最短步数即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=30+5;
const ll MAXQ=500+5;
ll n,m,Q;
bool gd[MAXN][MAXN];
ll dx[]={0,0,1,-1},dy[]={1,-1,0,0};
bool cg(ll x,ll y){
	return x>0&&x<=n&&y>0&&y<=m&&gd[x][y];
}
bool vis[MAXN][MAXN];
struct node{
	ll x,y,tm;
};
ll bfs(ll cx,ll cy,ll sx,ll sy,ll ex,ll ey){
	queue<node>q;
	memset(vis,false,sizeof(vis));
	q.push({sx,sy,0});
	vis[sx][sy]=true;
	if(sx==cx&&sy==cy){
		return 1e9;
	}
	while(!q.empty()){
		ll x=q.front().x,y=q.front().y,tm=q.front().tm;
		q.pop();
		if(x==ex&&y==ey){
			return tm;
		}
		for(int i=0;i<4;++i){
			ll u=x+dx[i],v=y+dy[i];
			if(cg(u,v)&&!vis[u][v]&&!(u==cx&&v==cy)){
				vis[u][v]=true;
				q.push({u,v,tm+1});
			}
		}
	}
	return 1e9;
}
ll val[MAXN][MAXN][4][4];
struct State{
	ll qx,qy,lst,tm;
	bool operator<(const State&K)const{
        if(tm==K.tm){
            if(qx==K.qx){
                if(qy==K.qy){
                    return lst<K.lst;
                }
                return qy<K.qy;
            }
            return qx<K.qx;
        }
		return tm>K.tm;
	}
};
bool vs[MAXN][MAXN][4];
ll dis[MAXN][MAXN][4];
void dijkstra(ll ex,ll ey,ll sx,ll sy,ll tx,ll ty){
	priority_queue<State>pq;
	memset(vs,false,sizeof(vs));
	memset(dis,0x3f,sizeof(dis));
	for(int i=0;i<4;++i){
		ll u=sx+dx[i],v=sy+dy[i];
		if(!cg(u,v)){
			continue;
		}
		ll w=bfs(sx,sy,ex,ey,u,v);
		if(w>=1e8){
			continue;
		}
		pq.push({sx,sy,i,w});
		dis[sx][sy][i]=w;
	}
	while(!pq.empty()){
		State sta=pq.top();
		pq.pop();
		ll x=sta.qx,y=sta.qy,lst=sta.lst;
		if(vs[x][y][lst]){
			continue;
		}
		vs[x][y][lst]=true;
		for(int i=0;i<4;++i){
			ll u=x+dx[i],v=y+dy[i];
			ll w=val[x][y][lst][i];
			if(w>1e8){
				continue;
			}
			ll nlst;
			if(i==0){
				nlst=1;
			}else if(i==1){
				nlst=0;
			}else if(i==2){
				nlst=3;
			}else{
				nlst=2;
			}
			if(dis[x][y][lst]+w+1<dis[u][v][nlst]){
				dis[u][v][nlst]=dis[x][y][lst]+w+1;
				pq.push({u,v,nlst,dis[u][v][nlst]});
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>Q;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>gd[i][j];
		}
	}
	memset(val,0x3f,sizeof(val));
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(!cg(i,j)){
				continue;
			}
			for(int k=0;k<4;++k){
				ll x=i+dx[k],y=j+dy[k];
				if(!cg(x,y)){
					continue;
				}
				for(int l=0;l<4;++l){
					if(k==l){
						val[i][j][k][l]=0;
						continue;
					}
					ll u=i+dx[l],v=j+dy[l];
					if(!cg(u,v)){
						continue;
					}
					val[i][j][k][l]=bfs(i,j,x,y,u,v);
				}
			}
		}
	}
	while(Q--){
		ll ex,ey,sx,sy,tx,ty;
		cin>>ex>>ey>>sx>>sy>>tx>>ty;
		if(sx==tx&&sy==ty){
			cout<<0<<endl;
			continue;
		}
		if(!cg(sx,sy)||!cg(tx,ty)){
			cout<<-1<<endl;
			continue;
		}
		dijkstra(ex,ey,sx,sy,tx,ty);
        ll ans=min({dis[tx][ty][0],dis[tx][ty][1],dis[tx][ty][2],dis[tx][ty][3]});
		if(ans>1e8){
			cout<<-1<<endl;
		}else{
			cout<<ans<<endl;
		}
	};
	return 0;
}