Cool, It’s Yesterday Four Times More

watersail / 2024-11-05 / 原文

考虑朴素算法的缺陷之处在于，对于两对相对位置一致且两两连通的袋鼠，朴素算法重复计算了多次
记录状态(i,j,i’,j’)，搜索即可
可以通过一遍bfs更新。更简便的方法是，取当前元素作为当前连通块的代表元素，在bfs的过程中顺便给连通块内的所有状态染上相应的颜色

点击查看代码

#include <bits/stdc++.h>
using namespace std;
bool f[1005][1005];
bool b[1005][1005];
int v[5005][5005];
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
int n,m;
int id(int i,int j)
{
	return (i-1)*m+j;
}
int ans,x,y;
bool dfs(int i1,int j1,int i2,int j2)
{
	if(!f[i1][j1])
	{
		return false;
	}
	if(f[i1][j1]&&!f[i2][j2])
	{
		return true;
	}
	b[x][y]=true;
	for(int i=0;i<4;i++)
	{
		x+=dx[i];
		y+=dy[i];
		if(b[x][y]==false)
		{
			v[id(i1,j1)][id(i2,j2)]|=dfs(i1+dx[i],j1+dy[i],i2+dx[i],j2+dy[i]);
		}
		y-=dy[i];
		x-=dx[i];
	}
	return v[id(i1,j1)][id(i2,j2)];
}
void update(int i1,int j1,int i2,int j2,int val)
{
	if(!f[i1][j1])
	{
		return;
	}
	if(f[i1][j1]&&!f[i2][j2])
	{
		return;
	}
	if(!b[x][y])
	{
		return;
	}
	v[id(i1,j1)][id(i2,j2)]=val;
	b[x][y]=false;
	for(int i=0;i<4;i++)
	{
		x+=dx[i];
		y+=dy[i];
		update(i1+dx[i],j1+dy[i],i2+dx[i],j2+dy[i],val);
		y-=dy[i];
		x-=dx[i];
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				char c;
				cin>>c;
				if(c=='.')
				{
					f[i][j]=true;
				}
			}
		}
		for(int i=1;i<=n*m;i++)
		{
			for(int j=1;j<=n*m;j++)
			{
				v[i][j]=0;
			}
		}
		ans=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(f[i][j])
				{
					bool pd=true;
					for(int k=1;k<=n;k++)
					{
						for(int l=1;l<=m;l++)
						{
							if(f[k][l]&&id(i,j)!=id(k,l))
							{
								if(!v[id(i,j)][id(k,l)])
								{
									x=y=0;
									dfs(i,j,k,l);
									if(v[id(i,j)][id(k,l)]==0)
									{
										v[id(i,j)][id(k,l)]=-1;
									}
									update(i,j,k,l,v[id(i,j)][id(k,l)]);
								}
								if(v[id(i,j)][id(k,l)]==-1)
								{
									pd=false;
								}
							}
						}
					}
					ans+=(pd==true);
				}
			}
		}
		cout<<ans<<"\n";
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				f[i][j]=false;
			}
		}
	}
	return 0;
}