- 仓库货位
tj拉完了
- @ 2026-9-19 9:50:46
我们直接考虑 什么时候贡献答案,当且仅当
-
。
-
将 设为 后,令
$$\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}$$存在 , 到 不存在路径,这里显然直接
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
- 上传者