B4347 [语言月赛 202506] 贴纸画 题解

· · 题解

Source & Knowledge

2025 年 6 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

给定一张 n 行 m 列的空白画纸，一张 c 行 c 列的图案纸，以及 k 张透明贴纸。每张贴纸有其粘贴区域、取图的图案纸左上角坐标以及一个重要性 p 值。贴纸会按顺序贴到画纸上。当多张贴纸覆盖同一个格子时，重要性数值更大的贴纸会覆盖在上面。最终输出画纸的颜色状态，未覆盖的格子用 -1 表示。

题目分析

本题的核心是二维数组的覆盖与优先级处理。由于存在覆盖关系，并且优先级由重要性数值决定，我们使用以下策略：对于画纸上的每一个格子，我们遍历所有可能覆盖它的贴纸。在这些贴纸中，我们选择重要性最高的那一张来决定这个格子的最终颜色。

具体来说，对于画纸上的每一个格子 (r, col)：

  1. 初始化：将其颜色设置为 -1，表示未被覆盖。同时，记录当前格子的“最高重要性”为一个足够小的值。
  2. 遍历贴纸：遍历输入的 k 张贴纸。
    • 判断覆盖：检查当前贴纸是否覆盖了格子 (r, col)。这可以通过判断 (r, col) 是否落在贴纸的矩形区域 (x_1, y_1) 到 (x_2, y_2) 内部来实现。即 x_1 \le r \le x_2 且 y_1 \le col \le y_2。
    • 更新颜色：如果当前贴纸覆盖了格子 (r, col)，并且它的重要性 p 大于当前格子记录的“最高重要性”：
      • 更新格子的颜色为当前贴纸在图案纸上对应的颜色。
      • 更新格子的“最高重要性”为当前贴纸的 p 值。

我们可以使用一个 n \times m 的二维数组 f[MAXN][MAXM] 来存储画纸的最终颜色，并将其所有元素初始化为 -1。然后，使用嵌套循环遍历画纸上的每一个格子 (r, col)：

// 假设画纸大小为 n*m, 图案纸为 tex[MAXC][MAXC], 贴纸信息为 struct v[MAXK]，这些信息都已经读入。
// f[MAXN][MAXM] 存储最终结果

// 1. 初始化画纸为 -1
for (int r = 1; r <= n; ++r) {
    for (int col = 1; col <= m; ++col) {
        f[r][col] = -1;
    }
}

// 2. 遍历画纸上的每一个格子
for (int r = 1; r <= n; ++r) {
    for (int col = 1; col <= m; ++col) {
        int max_importance = 0; // 记录当前格子 (r, col) 遇到的最大重要性
        // 初始时，格子是 -1，重要性视为 0（任何贴纸都比它重要）

        // 3. 遍历所有贴纸
        for (int i = 1; i <= k; ++i) { // 遍历第 i 张贴纸
            // 获取当前贴纸的信息
            int x1 = v[i].x1;
            int y1 = v[i].y1;
            int x2 = v[i].x2;
            int y2 = v[i].y2;
            int p = v[i].p;
            int xt_start = v[i].xt;
            int yt_start = v[i].yt;

            // 4. 判断当前贴纸是否覆盖格子 (r, col)
            if (r >= x1 && r <= x2 && col >= y1 && col <= y2) {
                // 如果覆盖，且当前贴纸的重要性更高
                if (p > max_importance) {
                    // 更新当前格子的最高重要性
                    max_importance = p;

                    // 计算当前格子 (r, col) 对应图案纸上的坐标
                    int rt = xt_start + (r - x1);
                    int colt = yt_start + (col - y1);

                    // 更新画纸上此格子的颜色
                    f[r][col] = tex[rt][colt];
                }
            }
        }
    }
}