组合练习笔记：一个优雅的立方体构造

sunnywan · 2025-03-27 17:10:48 · 算法·理论

组合练习笔记：一个优雅的立方体构造

2025/03/26 记

2025/04/03 upd 感谢 InQueue 指出 n=5,7 层次图出错，已修改。

问题：有一个 n\times n\times n 的立方体，初始其所有 n^3 个单位立方体都是透明的，你需要将其中 k 个单位立方体染黑，使得其从正面侧面上面看都是 n\times n 的黑色正方形，且满足所有染黑了的单位立方体按面连通，求最小的 k。

时间：3 小时。

思路

简记染黑的单位立方体为方块。

先随便构造试试，可以用三片 n\times n\times 1 的板子并起来就可以挡住三个方向上的视线，共 3n^2-3n+1 个方块，所以 k\le 3n^2-3n+1。

然后意识到找上界好像没什么用，尝试分析一下下界。

想象从三个方向看过去，会看到一些方块，一个想法是把视线（某方向看到的面）看作贡献摊到被看到的单位立方体上。具体一点就是说，三个方向总共会看到 3n^2 个面，一个方块可以提供 3 个被看到的面。此时已经可以得到显然的结论 k\ge n^2，但是还需要考虑所有方块连通这个限制，我们尝试用这个视角分析连通可能带来的损失（也就是那些没被看到的面）。

会出现没被看到的面是因为，一个视线的方向上有多个方块所以只能看到第一个方块，此时损失可以分为两种：第一种损失是面相邻，每次两个方块面相邻都会藏起来一个面。第二种损失是隔空挡住，就是两个方块在某两个维度上坐标相同但是不相邻，这样也会挡住一个面。

考虑理想情况，就是所有方块通过恰好 k-1 次面向邻连通（最小化第一种损失，方块的面相邻关系形成树），并且不出现隔空挡住（没有第二种损失，不存在隔空阻挡）。那么 k 个方块提供了 3k-(k-1) 个面，要被看到 3n^2 个面。

发现在 n 为偶数的情况无法取到理论最小值，说明一定会出现某种损失（要么有环，要么存在隔空阻挡），但是反过来，如果我们找到了某个构造，其方块联通关系形成树，且不存在隔空阻挡，则一定是最优解。

尝试构造 n 较小情况，对于 n=3 最少用 13 个方块，然后我花了很久找到了这个最优解：

上图显示了每一层方块的布置。每个方向看都是 n\times n 正方形等价于：每层的每行每列都有方块，且所有层的并是 n\times n 的正方形。

猜测 n 为奇数时存在理论最优解。在寻找 n=5 的时候难度骤增，因为限制实在是太紧了，而且 n=3 的特殊解好像没有明显的规律。

要相信限制到极致的构造是具有某种美感的。于是我们逆向思考，什么样的结构是具有美感的？最优解利用了什么样的性质？然后按着这个感觉去构造。

思路一，贪吃蛇：这里的观察是，如果有两个方块在同一个视线方向上，则它们之间一条都必须是方块（不然就会出现隔空阻挡）。那么猜测方块连通形态大概是一条链，从某个起点开始向贪吃蛇一样遍历每层的对角，这样就可以保证每个方向都是连续的不会有隔空阻挡。主要是贪吃蛇可以非常好的利用方块棱相邻（如下图）。但是这种螺旋遍历的结构好像总是漏掉一条边。战斗一小时无果，如果有高手这样做出来了可以教教我吗？

思路二，中心轴：方块位置形如树，那么这棵树是怎么长出来的呢？感觉上会存在一个中心，然后树按着某种对称规律往外长。但是如果放置如下图的三个坐标轴方向的骨架，会发现直接就无法操作了（接下来怎么放都会出现环或者隔空阻挡）。于是中心不能是一个点，猜测是一根轴。

可以仿照 n=3 的解，选择其中两层往外枝，此时轴再其他层就不能枝了（不然就会形成环或者隔空阻挡），然后为了让其它层（下图 1, 3 层）也能帮忙覆盖，对于枝出去的两层（下图 2, 4 层）用 Z 形状（下图黑色）拐到别的层。照着这个感觉就捯饬出了这样一组 5\times 5 的构造：

本质上我们在做的是将平面分为（下图）两对对角区域，然后用四个“屋檐”覆盖，这样就解决了 n\times n\times (n-1) 的区域，最后上面加一层对角线就好：

于是我们就可以类似的构造出 n 为其它奇数时的最优解（n=5 新增蓝色，n=7 新增紫色）：

下面是 n=11 时的 3D 效果图：

对于偶数的 n 只需要类似的加半圈屋檐就好啦~

极致是具有某种美感的。