题解：P14422 [JOISC 2014] 水桶 / Water Bottle

#include<bits/stdc++.h>
using namespace std;
const int QAQ=2100,ovo=QAQ*QAQ;
int n,m,p,q;
inline int id(int x,int y) {return x*m+y;}
char wor[QAQ][QAQ];
const int TAT=2e5+19,roxy=5100,inf=2e9;
int x[TAT],y[TAT],dy[QAQ][QAQ],cb[QAQ][QAQ],f[TAT],siz[TAT];
struct xxx {int x,y,bu,id;} ;
bitset<QAQ> vis[QAQ];
queue<xxx> dui;
unordered_map<int,int> dis[TAT];
struct bbb {int u,v;} ;
vector<bbb> ccx[ovo];
void pao()
{
	while(!dui.empty())
	{
		xxx nw=dui.front();dui.pop();
		if(nw.x-1>=1&&wor[nw.x-1][nw.y]!='#')
		{
			if(!vis[nw.x-1][nw.y])
			{
				dui.push({nw.x-1,nw.y,nw.bu+1,nw.id}),vis[nw.x-1][nw.y]=1;
				dy[nw.x-1][nw.y]=nw.id;
				cb[nw.x-1][nw.y]=nw.bu+1;
			}
			else if(dis[nw.id].find(dy[nw.x-1][nw.y])==dis[nw.id].end())
			{
				dis[nw.id][dy[nw.x-1][nw.y]]=dis[dy[nw.x-1][nw.y]][nw.id]=1,
				ccx[nw.bu+cb[nw.x-1][nw.y]].push_back({nw.id,dy[nw.x-1][nw.y]});
			}
		}
		if(nw.x+1<=n&&wor[nw.x+1][nw.y]!='#')
		{
			if(!vis[nw.x+1][nw.y])
			{
				dui.push({nw.x+1,nw.y,nw.bu+1,nw.id}),vis[nw.x+1][nw.y]=1;
				dy[nw.x+1][nw.y]=nw.id;
				cb[nw.x+1][nw.y]=nw.bu+1;
				
			}
			else if(dis[nw.id].find(dy[nw.x+1][nw.y])==dis[nw.id].end())
			{
				dis[nw.id][dy[nw.x+1][nw.y]]=dis[dy[nw.x+1][nw.y]][nw.id]=1,
				ccx[nw.bu+cb[nw.x+1][nw.y]].push_back({nw.id,dy[nw.x+1][nw.y]});
			}
		}
		if(nw.y-1>=1&&wor[nw.x][nw.y-1]!='#')
		{
			if(!vis[nw.x][nw.y-1])
			{
				dui.push({nw.x,nw.y-1,nw.bu+1,nw.id}),vis[nw.x][nw.y-1]=1;
				dy[nw.x][nw.y-1]=nw.id;
				cb[nw.x][nw.y-1]=nw.bu+1;
				
			}
			else if(dis[nw.id].find(dy[nw.x][nw.y-1])==dis[nw.id].end())
				dis[nw.id][dy[nw.x][nw.y-1]]=dis[dy[nw.x][nw.y-1]][nw.id]=1,
				ccx[nw.bu+cb[nw.x][nw.y-1]].push_back({nw.id,dy[nw.x][nw.y-1]});
		}
		if(nw.y+1<=m&&wor[nw.x][nw.y+1]!='#')
		{
			if(!vis[nw.x][nw.y+1])
			{
				dui.push({nw.x,nw.y+1,nw.bu+1,nw.id}),vis[nw.x][nw.y+1]=1;
				dy[nw.x][nw.y+1]=nw.id;
				cb[nw.x][nw.y+1]=nw.bu+1;
			}
			else if(dis[nw.id].find(dy[nw.x][nw.y+1])==dis[nw.id].end())
				dis[nw.id][dy[nw.x][nw.y+1]]=dis[dy[nw.x][nw.y+1]][nw.id]=1,
				ccx[nw.bu+cb[nw.x][nw.y+1]].push_back({nw.id,dy[nw.x][nw.y+1]});
		}
	}
}
struct wen {int u,v,id;} d[TAT],o1[TAT],o2[TAT];


int find(int x) {return x==f[x]?x:find(f[x]);}
struct ccc {int x,f,siz;} ;
vector<ccc> che[ovo];

void hebing(int x,int y,int z)
{
	x=find(x),y=find(y);
	if(x==y) return ;
	che[z].push_back({x,f[x],siz[x]});
	che[z].push_back({y,f[y],siz[y]});
	if(siz[x]>siz[y]) swap(x,y);
	f[x]=y;
	siz[y]+=(siz[x]==siz[y]);
}
int ans[TAT],zz=-1;
void chuli(int l,int r,int L,int R)
{
	if(L>R) return ;
	if(l==r)
	{
		for(int i=L;i<=R;i++) ans[d[i].id]=l;
		return ;
	}
	int mid=(l+r)>>1;
	while(zz<mid)
	{
		++zz;
		for(bbb nw:ccx[zz]) hebing(nw.u,nw.v,zz);
	}
	while(zz>mid)
	{
		if(che[zz].size()>0)
		{
			for(int i=che[zz].size()-1;i>=0;i--)
				f[che[zz][i].x]=che[zz][i].f,siz[che[zz][i].x]=che[zz][i].siz;
			che[zz].clear();
		}
		zz--;
	}
	
	
	int cnt1=0,cnt2=0;
	for(int i=L;i<=R;i++)
	{
		if(find(d[i].u)==find(d[i].v)) o1[++cnt1]=d[i];
		else o2[++cnt2]=d[i];
	}
	for(int i=1;i<=cnt1;i++) d[L+i-1]=o1[i];
	for(int i=1;i<=cnt2;i++) d[L+cnt1+i-1]=o2[i];
	
	chuli(l,mid,L,L+cnt1-1),chuli(mid+1,r,L+cnt1,R);
}

signed main()
{
	freopen("dydx.in","r",stdin);
	freopen("dydx.out","w",stdout);
	
	scanf("%d%d%d%d",&n,&m,&p,&q);
	for(int i=1;i<=n;i++) scanf("%s",wor[i]+1);
	for(int i=1;i<=p;i++)
		scanf("%d%d",&x[i],&y[i]),dui.push({x[i],y[i],0,i}),
		vis[x[i]][y[i]]=1,wor[x[i]][y[i]]='F',dy[x[i]][y[i]]=i,dis[i][i]=1;
	
	pao();
	
	
	
	for(int i=1;i<=p;i++) f[i]=i,siz[i]=1;
	
	for(int i=1;i<=q;i++) scanf("%d%d",&d[i].u,&d[i].v),d[i].id=i;
	
	
	int jx=n*m+1;
	chuli(0,jx,1,q);
	
	for(int i=1;i<=q;i++)
	{
		if(ans[i]==jx) printf("-1\n");
		else printf("%d\n",ans[i]);
	}
	
	return 0;
}