P10232 [COCI 2023/2024 #4] Roboti 题解

知识点

简单环，DFS。

题意分析

在 \(n\) 行，\(m\) 列的网格里，给定 \(k\) 个转弯点，再给定 \(Q\) 个询问，问每次从某个坐标到另一个坐标的最少转弯次数，或者判断不可能到达。

思路分析

我们发现在一个点坐标与方向确定的时候，到达的下一个点的坐标与方向一定确定，那我们把每个转弯点拆成四个方向不同的点，分别判断，那么整个图就变成了一堆简单环，那么两个点的距离就很容易得到，判断合法也只要看是不是在一个环里即可。

CODE

#include<bits/stdc++.h>
#define Fi first
#define Se second
#define endl '\n'
#define INF 0x3f3f3f3f
#define Pii pair<int,int>
#define All(a) begin(a),end(a)
#define tomax(a,b) ((a)=max((a),(b)))
#define tomin(a,b) ((a)=min((a),(b)))
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define DOR(i,a,b) for(register int i=(a);i>=(b);--i)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=1e5+10,M=1e6+10,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
bool ti[N];
bool vis[N][4];
int n,m,k,Q,cnt;
int x[N],y[N],siz[N<<2];
int id[N][4],dep[N][4];
Pii p[4][2],fa[N][4];
vector< Pii > X[M],Y[M];
int nxt(int x,int y,int d){
	Pii cur={d&1?x:y,d<2?INF:0};
	auto it=d&1?lower_bound(All(Y[y]),cur):lower_bound(All(X[x]),cur);
	auto it1=d&1?Y[y].begin():X[x].begin(),it2=d&1?Y[y].end():X[x].end();
	if(d<2)swap(it1,it2);
	if(it==it1)it=it2;
	if(it==it1)return -1;
	if(d>1)--it;
	return it->Se;
}
void dfs(int u,int d){
	Pii v=fa[u][d];
	vis[u][d]=1,id[u][d]=cnt,++siz[cnt];
	if(~v.Fi&&!vis[v.Fi][v.Se])dep[v.Fi][v.Se]=dep[u][d]+1,dfs(v.Fi,v.Se);
}
int dis(Pii a,Pii b){
	if(id[a.Fi][a.Se]!=id[b.Fi][b.Se])return INF;
	return (dep[b.Fi][b.Se]-dep[a.Fi][a.Se]+siz[id[a.Fi][a.Se]])%siz[id[a.Fi][a.Se]];
}
signed main(){
	cin>>n>>m>>k;
	FOR(i,1,k){
		char c;
		cin>>x[i]>>y[i]>>c,ti[i]=(c=='L'),X[x[i]].push_back({y[i],i}),Y[y[i]].push_back({x[i],i});
	}
	FOR(i,1,n)sort(All(X[i]));
	FOR(i,1,m)sort(All(Y[i]));
	FOR(i,1,k)FOR(d,0,3){
		int _d=ti[i]?(d+3)%4:(d+1)%4;
		fa[i][d]={nxt(x[i],y[i],_d),_d};
	}
	FOR(i,1,k)FOR(d,0,3)if(!vis[i][d])++cnt,dfs(i,d);
	cin>>Q;
	while(Q--){
		int xa,ya,xb,yb,ans=INF;cin>>xa>>ya>>xb>>yb;
		FOR(d,0,3)p[d][0]={nxt(xa,ya,d),d},p[d][1]={nxt(xb-dx[d],yb-dy[d],d),d};
		FOR(d,0,3)if(~p[d][0].Fi)FOR(_d,0,3)if(~p[_d][1].Fi)tomin(ans,dis(p[d][0],p[_d][1]));
		if(xa==xb&&X[xa].empty()||ya==yb&&Y[ya].empty())ans=0;
		cout<<(ans<INF?ans:-1)<<endl;
	}
	return 0;
}
/*
首先，拆点，把每个转折点拆成 4 个方向，然后我们发现，如果一个点有出入度，那么必定是一个出度和一个入度，
所以问题就转化为了一堆简单环上判断距离，直接求解即可。
*/