【深基5.例7】工艺品制作

解题思路

用三维布尔数组记录哪些小方块已被切除。每次枚举切割范围设为 true，最后统计仍为 false 的位置。

正确性说明

布尔标记表示所有切割区域的并集，重复切除不会多计。未被任何切割覆盖的位置恰好是剩余体积。

易错点

范围含两个端点；切割重叠时不能直接重复减体积。

复杂度

时间 O((q+1)wxh)，空间 O(wxh)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int w, x, h, q;
    cin >> w >> x >> h >> q;
    static bool cut[21][21][21] = {};
    while (q--) {
        int a, b, c, d, e, f;
        cin >> a >> b >> c >> d >> e >> f;
        for (int i = a; i <= d; i++)
            for (int j = b; j <= e; j++)
                for (int k = c; k <= f; k++)
                    cut[i][j][k] = true;
    }
    int ans = 0;
    for (int i = 1; i <= w; i++)
        for (int j = 1; j <= x; j++)
            for (int k = 1; k <= h; k++)
                if (!cut[i][j][k])
                    ans++;
    cout << ans << "\n";
    return 0;
}