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

题意

一个 w * x * h 的长方体由很多 1 * 1 * 1 小方块组成。每次切割给出一个三维闭区间，把区间内所有小方块蒸发掉。问所有切割后还剩多少小方块。

思路

数据范围很小：三维尺寸都不超过 20。可以直接开三维布尔列表 removed，表示每个坐标的小方块是否被切掉。

每次切割给出：

text

1x1 y1 z1 x2 y2 z2

就用三重循环枚举这个小长方体内的所有坐标，把它们标成 True。

所有切割完成后，再枚举整个长方体，统计仍为 False 的小方块数量。

这题是三维数组模拟，正解就是直接标记，不创建 brute.py。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：用 map(int, input().split()) 读取一行多个整数。
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：三重 range 循环可以直接枚举三维坐标。
三维列表要用嵌套推导式创建，避免多个层共享同一个子列表。
本题坐标从 1 开始，所以列表大小开到 维度 + 1。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23width, depth, height = map(int, input().split())
cut_count = int(input())

removed = [
    [[False for _ in range(height + 1)] for _ in range(depth + 1)]
    for _ in range(width + 1)
]

for _ in range(cut_count):
    x1, y1, z1, x2, y2, z2 = map(int, input().split())
    for x in range(x1, x2 + 1):
        for y in range(y1, y2 + 1):
            for z in range(z1, z2 + 1):
                removed[x][y][z] = True

answer = 0
for x in range(1, width + 1):
    for y in range(1, depth + 1):
        for z in range(1, height + 1):
            if not removed[x][y][z]:
                answer += 1

print(answer)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

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

int w, d, h; // 长方体的长、深、高
bool removed[25][25][25]; // 被切掉的小方块
int q, ans;

int main() {
    cin >> w >> d >> h >> q;
    int x1, y1, z1, x2, y2, z2;
    for (int k = 1; k <= q; k++) {
        cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
        // 标记被切掉的区域
        for (int x = x1; x <= x2; x++)
            for (int y = y1; y <= y2; y++)
                for (int z = z1; z <= z2; z++)
                    removed[x][y][z] = true;
    }
    // 统计剩余小方块
    for (int x = 1; x <= w; x++)
        for (int y = 1; y <= d; y++)
            for (int z = 1; z <= h; z++)
                if (!removed[x][y][z]) ans++;
    cout << ans;
    return 0;
}

Pythonic 写法

用 product 生成被切坐标集合，体积减去去重后的点数：

python

1
2
3
4
5
6
7
8
9from itertools import product

w, d, h = map(int, input().split())
q = int(input())
removed = set()
for _ in range(q):
    x1, y1, z1, x2, y2, z2 = map(int, input().split())
    removed |= set(product(range(x1, x2 + 1), range(y1, y2 + 1), range(z1, z2 + 1)))
print(w * d * h - len(removed))

复杂度

设体积为 V = w*x*h。每次切割最多枚举 V 个小方块，时间复杂度上界是 $O(qV)$ ；最后统计是 $O(V)$ 。空间复杂度是 $O(V)$ 。

总结

当数据规模很小时，直接用三维列表模拟最清楚。重点是坐标范围包含端点，并且不要用错误的列表乘法创建三维数组。

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

目录

题意

思路

Python 知识

代码

Pythonic 写法

复杂度

总结