我们直接考虑 (i,j,k)(i,j,k) 什么时候贡献答案,当且仅当

  1. ai,j,k=1a_{i,j,k}=1

  2. ai,j,ka_{i,j,k} 设为 00 后,令

    $$\begin{aligned} S&=\{(i-1,j,k),(i,j-1,k),(i,j,k-1)\}\\ T&=\{(i+1,j,k),(i,j+1,k),(i,j,k+1)\}\\ s&=\{x \in S \mid x \text{的位置满足条件},\ a_x = 1\}\\ t&=\{x \in T \mid x \text{的位置满足条件},\ a_x = 1\} \end{aligned}$$

    存在 xs,ytx\in s,y\in txxyy 不存在路径,这里显然直接 dfs

代码实现:

#include<bits/stdc++.h>
using namespace std;
const int MAXN=105;
int n,m,d;
int a[MAXN][MAXN][MAXN];

inline bool ch(int i,int j,int k) // 检查一个点是否在范围内
{
	if(i<1||i>n||j<1||j>m||k<1||k>d) return 0;
	return 1;
}

inline bool ch(array<int,3> s) {return ch(s[0],s[1],s[2]);} // 检查一个点是否在范围内

inline int aa(array<int,3> s) {return a[s[0]][s[1]][s[2]];} // 查询一个点的值

bool dfs(int x,int y,int z,int xx,int yy,int zz,int dep=0)
{
	if(!ch(x,y,z)) return 0;
	if(!a[x][y][z]) return 0;
	if(x>xx||y>yy||z>zz) return 0;
	if(dep>2) return 0;
	if(x==xx&&y==yy&&z==zz) return 1;
	return dfs(x+1,y,z,xx,yy,zz,dep+1)|dfs(x,y+1,z,xx,yy,zz,dep+1)|dfs(x,y,z+1,xx,yy,zz,dep+1);
} // dfs 判断 (x,y,z) -> (xx,yy,zz) 是否有路径

int get(array<int,3> s)
{
	for(int d:{0,1,2}) // 构造 S
	{
		auto ss=s; ss[d]--; // 构造 s
		if(!ch(ss)||!aa(ss)) continue;
		for(int dd:{0,1,2}) // 构造 T
		{
			auto t=s; t[dd]++; // 构造 t
			if(!ch(t)||!aa(t)) continue;
			if(!dfs(ss[0],ss[1],ss[2],t[0],t[1],t[2])) return 1; // 判断
		}
	}
	return 0;
}

void solve()
{
	cin>>n>>m>>d;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=d;k++) {char c;cin>>c,a[i][j][k]=c-'0';}
	int ans=0;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=d;k++) if(a[i][j][k])
	{
		a[i][j][k]=0;
		ans+=get({i,j,k});
		a[i][j][k]=1;
	}
	
	
	cout<<ans<<endl;
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	// int ttt; for(cin>>ttt;ttt--;)
	solve();
	return 0; 
}

0 条评论

目前还没有评论...

信息

ID
19865
时间
ms
内存
MiB
难度
显示难度暂无评定
标签
递交数
22
已通过
6
上传者