我们直接考虑 (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}$$

    存在 x∈s,y∈tx\in s,y\in t,xx 到 yy 不存在路径,这里显然直接 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; 
}

2 条评论

  • @ 2026-9-24 7:14:43

    写法挺好的。将前驱、后继之间的可达性判断交给 DFS,统一处理了直行与拐弯的情况,代码里可以少写一些分类讨论。

    但本质上这一题关键还是对于任意两点之间的必经性,缩到当前点的相邻前驱和后继。我认为这一点的证明才是题解里应该着重展示的~

    ps. 代码里的return dfs(...) | dfs(...) | dfs(...); 改成 return dfs(...) || dfs(...) || dfs(...); 似乎可以进行一些常数上的优化

    • @ 2026-9-22 12:48:00

      你咋这么强

      • 1

      信息

      ID
      19865
      时间
      ms
      内存
      MiB
      难度
      显示难度普及+/提高−
      标签
      递交数
      70
      已通过
      18
      上传者