CF638D Three-dimensional Turtle Super Computer

发布时间 2023-10-18 20:22:09作者: 空気力学の詩

什么大力爆搜题

不妨考虑枚举要拿掉的位置,考虑怎么检验它是某两个点之间必经之点

简单手玩一下会发现如果存在这么一条路径,那么我们一定可以把该路径的端点定为与要拿掉的点距离为\(1\)的点上(即与要拿掉的点上下左右前后\(6\)连通)

因此我们把这些点找出来后爆枚点对,判断路径是否唯一就直接爆搜即可

总复杂度大致为\(O(nmk\times 6^2)\),但实际跑不满可以轻松通过

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=105,dx[6]={1,0,-1,0,0,0},dy[6]={0,1,0,-1,0,0},dz[6]={0,0,0,0,1,-1};
int n,m,l,ans; char a[N][N][N];
inline bool Path(const tri& cur,const tri& tar)
{
	if (cur==tar) return true;
	for (RI i=0;i<3;++i) if (cur[i]<tar[i])
	{
		tri tmp=cur; ++tmp[i]; auto [x,y,z]=tmp;
		if (a[x][y][z]=='1'&&Path(tmp,tar)) return true;
	}
	return false;
};
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k,p,q; for (scanf("%d%d%d",&n,&m,&l),i=1;i<=n;++i)
	for (j=1;j<=m;++j) scanf("%s",a[i][j]+1);
	for (i=1;i<=n;++i) for (j=1;j<=m;++j)
	for (k=1;k<=l;++k) if (a[i][j][k]=='1')
	{
		vector <tri> pnt; bool flag=0;
		for (p=0;p<6;++p)
		{
			int nx=i+dx[p],ny=j+dy[p],nz=k+dz[p];
			if (nx<1||nx>n||ny<1||ny>m||nz<1||nz>l) continue;
			if (a[nx][ny][nz]=='1') pnt.push_back({nx,ny,nz});
		}
		for (p=0;p<pnt.size()&&!flag;++p) for (q=0;q<pnt.size()&&!flag;++q)
		if (p!=q&&pnt[p][0]<=pnt[q][0]&&pnt[p][1]<=pnt[q][1]&&pnt[p][2]<=pnt[q][2]&&Path(pnt[p],pnt[q]))
		{
			a[i][j][k]='0'; if (!Path(pnt[p],pnt[q])) flag=1; a[i][j][k]='1';
		}
		ans+=flag;
	}
	return printf("%d",ans),0;
}