自动搬运

查看原文

来自洛谷，原作者为

	Loser_King Just stay where you are; Let your fear subside

搬运于2025-08-24 21:51:35，当前版本为作者最后更新于2022-07-15 20:24:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

基础图论作业题。感觉难度不及黑？

可能是我之前写过这玩意或者现在的做法相对简单很多。

题意

给定一个长宽均为 $n$ 的黑白矩阵，你需要回答 $q$ 组询问：

给定起点坐标和终点坐标，你有一个初始中心在起点，边长为 $x$ 的正方形。在“存在一条从起点到终点的路径，使得正方形的中心在路径上移动时不碰到任何黑格子”的条件下，求出最大可能的奇整数 $x$。如果不存在，输出 $0$。

做法

感性理解有“路径上最宽的部分影响答案”，于是可以想到瓶颈路。

在这里给出一个复杂度较劣，但是相当好写的离线瓶颈路做法（基于 Kruskal，但是不需要用到 Kruskal 重构树相关知识）：

1. 将边按边权排序。

2. 维护 set<int>s[N]，对于每个询问 $x_i,y_i$，把询问编号 $i$ 插入对应的 set 中。

3. 按照边权顺序处理每一条边。对于一条边 $x\xleftrightarrow w y$，如果 $x,y$ 不在一个连通块内，启发式合并两个集合 $s_x,s_y$。如果 $s_x,s_y$ 中有相同元素，将两个元素同时删除，并标记该元素对应询问答案为 $w$。最后合并 $x,y$ 所在连通块。

时间复杂度 $O(q\log m\log q)$，$m$ 为边数，$q$ 为询问数。复杂度瓶颈为启发式合并和 set 的 insert 操作。

回到这个问题。首先用朴素的 DP 求出一个坐标可以拓展的最大正方形的边长 $w_{i,j}$。（左上，右上，左下，右下直接 DP，然后合并）然后套用上面的方法，将所有点按照 $w$ 降序排序，然后依次如上处理，向四个方向合并即可。

时间复杂度 $O(q\log n^2\log q)$，较题解区的 $O(n^2\log n^2)$ 劣。但是因为本题中 $q<n^2$ 且开了 4s，所以实际上跑起来也不会超时，但是好像卡到时限了。

代码

变量和上面数组对应。

没有刻意缩减代码，代码比题解代码短不少（很多重复），且保留了可读性。

//P3684 AC Code
//written by Loser_King(159686)
//C++14 (GCC 9) | 1.94KB | 7.93s | 112.96MB
#include<bits/stdc++.h>
#define ord(x,y) (((x)-1)*n+(y))
#define getx(k) (((k)-1)/n+1)
#define gety(k) (((k)-1)%n+1)
using namespace std;
int const N=1010,K=N*N,dx[]={-1,0,0,1},dy[]={0,-1,1,0};
int n,q,w[N][N],ul[N][N],ur[N][N],dl[N][N],dr[N][N],f[K],ans[K];
char a[N][N];
set<int>s[K];
pair<int,int>p[K];
int find(int x){
	return x^f[x]?f[x]=find(f[x]):x;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n*n;i++)
		f[i]=i;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(a[i][j]=='.')
				ul[i][j]=min(ul[i-1][j-1],
					min(ul[i][j-1],ul[i-1][j]))+1;
	for(int i=1;i<=n;i++)
		for(int j=n;j>=1;j--)
			if(a[i][j]=='.')
				ur[i][j]=min(ur[i-1][j+1],
					min(ur[i-1][j],ur[i][j+1]))+1;
	for(int i=n;i>=1;i--)
		for(int j=1;j<=n;j++)
			if(a[i][j]=='.')
				dl[i][j]=min(dl[i+1][j-1],
					min(dl[i+1][j],dl[i][j-1]))+1;
	for(int i=n;i>=1;i--)
		for(int j=n;j>=1;j--)
			if(a[i][j]=='.')
				dr[i][j]=min(dr[i+1][j+1],
					min(dr[i+1][j],dr[i][j+1]))+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			p[ord(i,j)]={w[i][j]=min(ul[i][j],min(ur[i][j],
				min(dl[i][j],dr[i][j])))*2-1,ord(i,j)};
	sort(p+1,p+1+n*n,greater<pair<int,int> >());
	cin>>q;
	for(int i=1;i<=q;i++){
		int ax,ay,bx,by;
		cin>>ax>>ay>>bx>>by;
		s[ord(ax,ay)].insert(i);
		s[ord(bx,by)].insert(i);
	}
	for(int i=1;i<=n*n;i++){
		int x=getx(p[i].second),y=gety(p[i].second),
			fa=find(p[i].second),k=p[i].first;
		if(a[x][y]=='#')
			continue;
		for(int j=0;j<4;j++){
			int tx=x+dx[j],ty=y+dy[j],tfa=find(ord(tx,ty));
			if(tx<1||ty<1||tx>n||ty>n||w[tx][ty]<w[x][y]||fa==tfa)
				continue;
			int fx=fa,fy=tfa;
			if(s[fx].size()>s[fy].size())
				swap(fx,fy);
			f[fx]=fa=fy;
			for(int w:s[fx])
				if(s[fy].count(w))
					ans[w]=k,s[fy].erase(w);
				else
					s[fy].insert(w);
			s[fx].clear();
		}
	}
	for(int i=1;i<=q;i++)
		cout<<ans[i]<<"\n";
}