「一本通 1.3 练习 2」平板涂色

题目描述

平面上有 $N$ 个互不覆盖的矩形，每个矩形由左上角 $(y_1,x_1)$ 、右下角 $(y_2,x_2)$ 坐标和颜色 $c$ 描述。涂色时必须等所有紧靠上方的矩形涂完后才能涂该矩形（ $u$ 的下底边与 $v$ 的上顶边共线且水平投影重叠）。每次拿起某种颜色的刷子，可以把当前所有可涂且颜色相同的矩形一次涂满；放下后再拿需重新计数。求涂完所有矩形的最少拿起刷子次数。

思路

$N<16$ ，用二进制掩码 $mask$ 记录已涂矩形。预处理每个矩形的紧靠上方矩形掩码 pre_mask。记忆化搜索 dfs(mask, cur_color)：若当前颜色还有可涂矩形，贪心全部涂完（不增加次数）；否则枚举所有可涂矩形的颜色换刷，代价 $+1$ 。

参考代码

Python 版：

python

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81#!/usr/bin/env python3
# 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-09-30 10:50
# update_at: 2026-09-30 10:50

import sys
from functools import cache

INF = 10**9


def build_pre_masks(rects: list[tuple[int, int, int, int, int]]) -> list[int]:
    """计算每个矩形必须在哪些矩形之后涂色：返回先决条件位掩码。

    当矩形 u 的下边界与矩形 v 的上边界贴合且水平区间重叠时，u 是 v 的直接上方矩形。
    """
    return [
        sum(
            1 << u
            for u, (uy1, ux1, uy2, ux2, _) in enumerate(rects)
            if uy2 == vy1 and not (ux2 <= vx1 or ux1 >= vx2)
        )
        for vy1, vx1, _, vx2, _ in rects
    ]


def min_brush_switches(n: int, rects: list[tuple[int, int, int, int, int]], pre_mask: list[int]) -> int:
    """记忆化搜索求涂满所有矩形的最少拿起刷子次数。"""
    target = (1 << n) - 1

    @cache
    def dfs(mask: int, cur_color: int) -> int:
        if mask == target:
            return 0

        # 当前可涂且与 cur_color 同色的矩形集合
        same_color = [
            i
            for i in range(n)
            if not (mask >> i & 1) and (mask & pre_mask[i]) == pre_mask[i] and rects[i][4] == cur_color
        ]
        if same_color:
            # 贪心：若手上有刷子且有同色可用，立刻全部涂掉不增加换刷次数
            nxt_mask = mask
            for i in same_color:
                nxt_mask |= 1 << i
            return dfs(nxt_mask, cur_color)

        # 换新颜色刷子：尝试所有当前上方依赖已全部涂好的可用颜色
        available = [
            i
            for i in range(n)
            if not (mask >> i & 1) and (mask & pre_mask[i]) == pre_mask[i]
        ]
        colors = {rects[i][4] for i in available}
        return min((1 + dfs(mask, c) for c in colors), default=INF)

    return dfs(0, 0)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    tokens = list(data)
    if not tokens:
        return
    it = iter(tokens)
    n = next(it)
    # y1, x1, y2, x2, color
    rects = [
        (next(it), next(it), next(it), next(it), next(it))
        for _ in range(n)
    ]
    pre_mask = build_pre_masks(rects)
    ans = min_brush_switches(n, rects, pre_mask)
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * 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-10-05 23:47
 * update_at: 2026-10-05 23:47
 */
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 16;
const int INF = 1e9;

int n;
// rects[i] = {y1, x1, y2, x2, color}
int rects[MAXN][5];
// pre_mask[i] 的第 u 位为 1 表示矩形 u 是 i 的紧靠上方矩形
int pre_mask[MAXN];
// memo[mask][color] 记忆化，color 范围 0..20，0 表示手中无刷子
int memo[1 << MAXN][21];
bool vis[1 << MAXN][21];

// 返回涂完剩余矩形所需的最少额外拿起刷子次数
int dfs(int mask, int cur_color) {
    if (mask == (1 << n) - 1) return 0;
    if (vis[mask][cur_color]) return memo[mask][cur_color];
    vis[mask][cur_color] = true;

    // 贪心：若手中有同色刷子，把所有可涂的同色矩形一次性涂完
    int nxt_mask = mask;
    for (int i = 0; i < n; ++i) {
        if ((mask >> i & 1)) continue;               // 已涂
        if ((mask & pre_mask[i]) != pre_mask[i]) continue; // 上方未涂完
        if (rects[i][4] != cur_color) continue;      // 颜色不同
        nxt_mask |= 1 << i;
    }
    if (nxt_mask != mask) {
        memo[mask][cur_color] = dfs(nxt_mask, cur_color);
        return memo[mask][cur_color];
    }

    // 枚举当前所有可涂矩形的颜色，换刷子
    int ans = INF;
    bool has_color[21] = {false};
    for (int i = 0; i < n; ++i) {
        if ((mask >> i & 1)) continue;
        if ((mask & pre_mask[i]) != pre_mask[i]) continue;
        int c = rects[i][4];
        if (!has_color[c]) {
            has_color[c] = true;
            ans = min(ans, 1 + dfs(mask, c));
        }
    }
    memo[mask][cur_color] = ans;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> rects[i][0] >> rects[i][1] >> rects[i][2] >> rects[i][3] >> rects[i][4];
    }
    // 预处理每个矩形的紧靠上方矩形掩码
    for (int v = 0; v < n; ++v) {
        int mask = 0;
        for (int u = 0; u < n; ++u) {
            if (rects[u][2] == rects[v][0]) { // u 的下边界贴合 v 的上边界
                if (!(rects[u][3] <= rects[v][1] || rects[u][1] >= rects[v][3])) {
                    mask |= 1 << u;
                }
            }
        }
        pre_mask[v] = mask;
    }
    cout << dfs(0, 0) << "\n";
    return 0;
}

「一本通 1.3 练习 2」平板涂色

目录

题目描述

思路

参考代码