P16379 [NordicOI 2026] Backrooms

有一个无限大的网格图，每个方格是空地或障碍。网格图的循环节是一个 $R \times C$ 的子网格，通过平移拼接进行重复。$q$ 次询问，每次给定两个空地 $(x_1,y_1),(x_2,y_2)$，判断两个点否四连通。$R,C \le 1000$，$q \le 10^5$，$0 \le x_1,y_1,x_2,y_2 \le 10^{12}$。

把那个 $R \times C$ 的重复单元称为一个单元。给单元也按照平面直角坐标系编号，称为单元坐标。

不跨边界的连通性是很好处理的。先不考虑边界，把所有连通块缩成一个点，并把在边界处相邻的点之间连边。这样只会有 $O(n)$ 条边。

我们发现在单个单元内上不连通的点可能通过边界连通，但走过去之后可能就不在同一个单元内了，会产生一定的单元偏移 $(dx,dy)$。这里的 $dx$ 和 $dy$ 的单位是单元边长而不是格。

如果我们从某个小格子出发，跨过若干边界后又回到了（相对位置的）起点，并且单元偏移 $(dx,dy) \neq (0,0)$，这就意味着我们可以无限走下去。假设起点的单元坐标是 $(x_0,y_0)$，那么我们可以走到所有 $(x_0+kdx,y_0+kdy)$ 单元的对应小方格，其中 $k$ 为整数。我们可以任取一棵生成树，然后把非树边产生的所有的环所对应的单元偏移加入线性基中以确定到底哪些单元中的这个方格可以被到达。

这很像一个向量基底问题，只不过线性组合是在整环上进行的。如果只有一个向量，那么是容易的；如果有至少两个线性无关的向量，那么由于是平面图，这些路径必然会相交，从而从任意一个单元能到所有其他单元。

那么我们只需要维护将整数向量插进线性基中，并判断能否用这些线性基拼凑出一个给定的整数向量。回答询问时，如果它们在原图上就不连通，那么答案为 No；否则先将它们移到同一相对位置的点上，计算出单元偏移，并判断这个连通块的线性基能否拼出这个向量即可。注意：本题的坐标系和二维数组的坐标系不同，可能需要进行转换。

::::info[代码]

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int ceil(int x,int y){return x/y+!!(x%y);}
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
void freopen(string file){freopen((file+".in").c_str(),"r",stdin);freopen((file+".out").c_str(),"w",stdout);}
int n,m,q;
char s[1020][1020];
int id[1020][1020],itot;
void dfs1(int x,int y)
{
	for(int d=0;d<4;d++)
	{
		int xx=x+dx[d],yy=y+dy[d];
		if(xx<1 || xx>n || yy<1 || yy>m) continue;
		if(s[xx][yy]=='#') continue;
		if(!id[xx][yy]) id[xx][yy]=id[x][y],dfs1(xx,yy);
	}
}
struct edge
{
	int to,vx,vy;
	edge(int to=0,int vx=0,int vy=0):to(to),vx(vx),vy(vy){}
};
vector<edge> e[1000020];
int fa[1000020],rt[1000020];
int disx[1000020],disy[1000020];
inline int gcd(int x,int y){x=abs(x);y=abs(y);static int z;while(y)z=x,x=y,y=z%y;return x;}
struct LinearBase
{
	int x1,y1;
	int x2,y2;
	void insert(int x,int y)
	{
		if(!x1 && !y1)
		{
			x1=x;y1=y;
			return;
		}
		if(x1*y==y1*x)
		{
			if(x1)
			{
				int xx=gcd(x1,x),yy=y1/(x1/xx);
				x1=xx;y1=yy;
			}
			else
			{
				int yy=gcd(y1,y),xx=x1/(y1/yy);
				x1=xx;y1=yy;
			}
			return;
		}
		x1=1;y1=0;
		x2=0;y2=1;
	}
	bool check(int x,int y)
	{
		if(!x1 && !y1) return x==0 && y==0;
		if(!x2 && !y2)
		{
			if(x1*y!=y1*x) return false;
			if(x1) return x%x1==0;
			else return y%y1==0;
		}
		return (x*y2-y*x2)%(x1*y2-y1*x2)==0;
	}
};
LinearBase bas[1000020];
void dfs2(int x,int f)
{
	fa[x]=f;
	rt[x]=f?rt[f]:x;
	for(edge v:e[x])
	{
		if(rt[v.to]) bas[rt[x]].insert(disx[x]+v.vx-disx[v.to],disy[x]+v.vy-disy[v.to]);
		else
		{
			disx[v.to]=disx[x]+v.vx;
			disy[v.to]=disy[x]+v.vy;
			dfs2(v.to,x);
		}
	}
}
bool query(int x1,int y1,int x2,int y2)
{
	if(rt[id[(x1-1)%n+1][(y1-1)%m+1]]!=rt[id[(x2-1)%n+1][(y2-1)%m+1]]) return false;
	int X=ceil(x2,n)-ceil(x1,n),Y=ceil(y2,m)-ceil(y1,m);
	x1=(x1-1)%n+1;x2=(x2-1)%n+1;y1=(y1-1)%m+1;y2=(y2-1)%m+1;
	X-=disx[id[x2][y2]]-disx[id[x1][y1]];
	Y-=disy[id[x2][y2]]-disy[id[x1][y1]];
	return bas[rt[id[x1][y1]]].check(X,Y);
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		static char op[1020];
		scanf("%s",op+1);
		for(int j=1;j<=m;j++) s[j][n-i+1]=op[j];
	}
	swap(n,m);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
	{
		if(s[i][j]=='#') continue;
		if(id[i][j]) continue;
		id[i][j]=++itot;
		dfs1(i,j);
	}
	for(int i=1;i<=n;i++)
	{
		if(s[i][1]=='.' && s[i][m]=='.')
		{
			e[id[i][1]].push_back(edge(id[i][m],0,-1));
			e[id[i][m]].push_back(edge(id[i][1],0,1));
		}
	}
	for(int j=1;j<=m;j++)
	{
		if(s[1][j]=='.' && s[n][j]=='.')
		{
			e[id[1][j]].push_back(edge(id[n][j],-1,0));
			e[id[n][j]].push_back(edge(id[1][j],1,0));
		}
	}
	for(int i=1;i<=itot;i++) if(!rt[i]) dfs2(i,0);
	cin>>q;
	for(int i=1,x1,y1,x2,y2;i<=q;i++)
	{
		scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
		x1++;y1++;x2++;y2++;
		printf(query(x1,y1,x2,y2)?"Yes\n":"No\n");
	}
}

::::