【Samara Farewell Contest 2020 C】Cyclically Shifted Maze 题解

题目大意

  给定一幅 $n \times m$ 的地图，地图由“.”和“#”构成，“.”表示空地，“#”表示障碍。
  求这个地图沿垂直和水平方向分别 shift 多少，能使空地形成一个连通块。求出所有可能的 shift 方案。

  $n,m \le 200$
  2s

$$\\$$ $$\\$$ $$\\$$

题解

  一开始想的是，把地图复制 4 份，然后在上面框出一个 $n \times m$ 的子矩阵使得空地是一个连通块。
  后来发现不用复制 4 份，可以看成是这个地图找一个垂直方向的分割线和一个水平方向的分割线，移动分割线时维护并查集。
  但无论如何总会遇到一个问题：要动态加边删边就很麻烦。

  于是题解给出了不用删边的办法。

  枚举上下方向的 shift，接着对于左右方向，对于每一个前缀都把它的并查集记录下来，每一个后缀也把它的并查集记录下来，这样使得后面可以枚举左右方向的分割线，然后合并前缀后缀并查集。
  记录并查集不需要把 $nm$ 个点都记下来，因为合并前缀后缀并查集只是在合并第一列和最后一列，因此前缀并查集只需把第一列的连通性记下来，后缀并查集只需把最后一列的连通性记下来。
  枚举上下方向的 shift 是 $O(n)$ 的，接着求前缀后缀并查集、枚举合并并查集都是 $O(n^2)$ 的，总的是 $O(n^3)$ 的。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=205;

int n,m;
char s[maxn][maxn];

int ga[maxn*maxn],num;
int get(int x) {return ga[x]==x ?x :ga[x]=get(ga[x]) ;}
void merge(int x,int y)
{
	x=get(x), y=get(y);
	if (x!=y) ga[x]=y, num--;
}
void clear_ga()
{
	for(int x=0; x<n*m; x++) ga[x]=x;
	num=0;
}

inline int id(int x,int y) {return x*m+y;}

int prega[maxn][maxn],sufga[maxn][maxn],prenum[maxn],sufnum[maxn];
vector<pair<int,int>> ans;
int main()
{
	scanf("%d %d",&n,&m);
	fo(i,0,n-1) scanf("%s",s[i]);
	
	for(int i=0; i<n; i++)
	{
		clear_ga();
		for(int j=0; j<m; j++)
		{
			for(int x=0; x<n; x++) num+=(s[(i+x)%n][j]=='.');
			for(int x=0; x<n; x++)
			{
				int curi=(i+x)%n;
				if (j && s[curi][j-1]=='.' && s[curi][j]=='.') merge(id(curi,j-1),id(curi,j));
				if (x<n-1 && s[curi][j]=='.' && s[(curi+1)%n][j]=='.') merge(id(curi,j),id((curi+1)%n,j));
			}
			for(int x=0; x<n; x++) prega[j][(i+x)%n]=get(id((i+x)%n,0));
			prenum[j]=num;
		}
		clear_ga();
		for(int j=m-1; j>=0; j--)
		{
			for(int x=0; x<n; x++) num+=(s[(i+x)%n][j]=='.');
			for(int x=0; x<n; x++)
			{
				int curi=(i+x)%n;
				if (j<m-1 && s[curi][j+1]=='.' && s[curi][j]=='.') merge(id(curi,j+1),id(curi,j));
				if (x<n-1 && s[curi][j]=='.' && s[(curi+1)%n][j]=='.') merge(id(curi,j),id((curi+1)%n,j));
			}
			for(int x=0; x<n; x++) sufga[j][(i+x)%n]=get(id((i+x)%n,m-1));
			sufnum[j]=num;
		}
		
		for(int j=0; j<m; j++)
		{
			if (j==0)
			{
				num=sufnum[j];
			} else
			{
				num=prenum[j-1]+sufnum[j];
				for(int x=0; x<n; x++)
				{
					int t=ga[id((i+x)%n,0)]=prega[j-1][(i+x)%n];
					ga[t]=t;
					t=ga[id((i+x)%n,m-1)]=sufga[j][(i+x)%n];
					ga[t]=t;
				}
				for(int x=0; x<n; x++)
					if (s[(i+x)%n][0]=='.' && s[(i+x)%n][m-1]=='.') merge(id((i+x)%n,0),id((i+x)%n,m-1));
			}
			if (num==1) ans.push_back(make_pair(i,j));
		}
	}
	
	printf("%d\n",ans.size());
	for(auto p:ans) printf("%d %d\n",p.first,p.second);
}