求调
查看原帖
求调
793095
ZR_BL楼主2024/10/24 22:11
#include<bits/stdc++.h>
#define cj(x,y) ((x-1)*m+y)
using namespace std;
const int N=502,M=3e5+5;
int n,m,q,x,y,z;

int f[N*N*6];
int get(int x){return f[x]==x?x:f[x]=get(f[x]);}

int num,cnt;

int lv,dm;

int mp[N*N];

int read(){char ch=getchar();while(1){if(ch=='.')return 1;if(ch=='v')return 2;if(ch=='#')return 3;ch=getchar();}}

struct edge{int h,t,cmp;}e[N*N*6];
void add(int x,int y,int d){e[++cnt]={x,y,d};}
bool cmp(edge x,edge y){return x.cmp>y.cmp;}

struct node{int h,t,nxt;}a[N*N*6];
int size,h[M],val[N*N*6];
void in(int x,int y){a[++size]={x,y,h[x]};h[x]=size;}

int fa[N*N*6][21],dep[N*N*6];

int dx[]={0,1,0,-1},dy[]={1,0,-1,0};

struct {int x,y;}qu[N*N];
int hd=1,tl,dis[N*N];
bitset<N*N>v;

void kruskal(){
	for(int i=1;i<=cnt;i++){
		int u=e[i].h,v=e[i].t;
		u=get(u),v=get(v);
		if(u!=v){
			in(++num,u),in(num,v);
			val[num]=e[i].cmp;
			num=get(num);
			fa[u][0]=num,fa[v][0]=num;
			f[u]=num,f[v]=num;
		}
	}
}

int lca(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i=20;i>=0;i--)if(dep[u]>=dep[v])u=fa[u][i];
	if(u==v)return u;
	for(int i=20;i>=0;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}

void dfs(int x,int fx){
	dep[x]=dep[fx]+1,fa[x][0]=fx;
	for(int i=h[x];i;i=a[i].nxt){
		int y=a[i].t;
		if(y!=fx)dfs(y,x);
	}
}

int main(){
	cin>>n>>m>>q;num=n*m*2;
	for(int i=1;i<=num*6;i++)f[i]=i;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			mp[cj(i,j)]=read();
			if(mp[cj(i,j)]==2)qu[++tl]={i,j},dis[cj(i,j)]=0,v[cj(i,j)]=1;
			if(mp[cj(i,j)]==3)lv=i,dm=j;
		}
	while(hd<=tl){
		for(int i=0;i<=3;i++){
			int xx=qu[hd].x+dx[i],yy=qu[hd].y+dy[i];
			if(xx<=0||yy<=0||xx>n||yy>m||v[cj(xx,yy)])continue;
			dis[cj(xx,yy)]=dis[cj(qu[hd].x,qu[hd].y)]+1;
			qu[++tl]={xx,yy};
			v[cj(xx,yy)]=1;
		}
		hd++;
	}
	for(int i=1;i<=n*m;i++)if(mp[i]==3)dis[i]=0;

	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int t=0;t<=1;t++){
				for(int k=0;k<=3;k++){
					int xx=i+dx[i],yy=j+dy[i];
					if(xx<=0||yy<=0||xx>n||yy>m||mp[cj(xx,yy)]==3)continue;
					if(j!=yy&&i>lv&&min(i,xx)<=dm&&max(i,xx)>dm){
						if(!t)add(cj(i,j),cj(xx,yy)+n*m,min(dis[cj(i,j)],dis[cj(xx,yy)]));
						else add(cj(i,j)+n*m,cj(xx,yy),min(dis[cj(i,j)],dis[cj(xx,yy)]));
					}
					else{
						if(!t)add(cj(i,j),cj(xx,yy),min(dis[cj(i,j)],dis[cj(xx,yy)]));
						else add(cj(i,j)+n*m,cj(xx,yy)+n*m,min(dis[cj(i,j)],dis[cj(xx,yy)]));
					}
				}
			}
		}
	}
	sort(e+1,e+cnt+1,cmp);
	kruskal();
	dfs(num,0);
	for(int i=1;i<=20;i++)
		for(int j=1;j<=num;j++)
			fa[j][i]=fa[fa[j][i-1]][i-1];
	for(int i=1;i<=q;i++){
		cin>>x>>y;
		cout<<val[lca(cj(x,y),cj(x,y)+n*m)]<<"\n";
	}
	return 0;
}
2024/10/24 22:11
加载中...