Griseo 的画作：用分枝限界法求颜料覆盖范围

Griseo 是黄金庭园的团宠小画家，最近她又开始了她的创作。由于 Griseo 画工强大，所以她只需要在画布（视为 n*m 的二维平面，坐标起始点为 1）的某处点上一笔，颜料就会依照 Griseo 的想法无尽扩散，颜料的扩散方式是这样的：

初始时颜料会向上扩散；2. 每个小时，颜料会根据 Griseo 的想法扩散 s[i] 的距离；3. 当该小时结束后，颜料将分裂成两部分，向左上角以及右上角移动（颜料必须走过 si 的距离才能向两边分裂）；

Griseo 想知道在每个小时末颜料的覆盖范围，以此推测画作的模样。

输入

第一行包含三个整数 n 、 m 、 t ，代表画布大小（n 行 m 列）和颜料扩散时间；

第二行包含 t 个整数 s[i]，代表第 i 个小时颜料扩散的距离；

第三行包含两个整数 x、y 代表颜料的初始位置。

输出

输出为一行，包含 t 个整数，第 i 个整数代表第 i 个小时末画布上颜料的覆盖范围。

使用分枝限界法解决该问题并给出 C++ 代码

分析

本题可以使用分枝限界法来解决。具体思路如下：

将当前覆盖范围看作一个节点，从起点开始，不断进行分裂，扩大当前覆盖范围。- 每次分裂后，分别计算左、右两个子节点的覆盖范围，将其加入待扩展节点队列。- 对于每个节点，记录其覆盖范围的左上角和右下角坐标，以便计算覆盖范围。- 当队列为空或已经扩展了 t 个小时时，结束搜索，输出所有扩展节点的覆盖范围。

具体实现细节见代码注释c++#include #include #include

using namespace std;

struct Node { int left_x, left_y, right_x, right_y; Node(int left_x, int left_y, int right_x, int right_y) : left_x(left_x), left_y(left_y), right_x(right_x), right_y(right_y) {}};

int main() { int n, m, t; cin >> n >> m >> t;

vector s(t); for (int i = 0; i < t; ++i) { cin >> s[i]; }

int x, y; cin >> x >> y;

queue q; q.push(Node(x, y, x, y)); // 初始化起点

vector area(t, 0); // 记录每个小时的覆盖范围

for (int hour = 0; hour < t; ++hour) { int q_size = q.size(); for (int i = 0; i < q_size; ++i) { Node cur = q.front(); q.pop();

  // 计算当前节点的覆盖范围      int left_x = max(1, cur.left_x - s[hour]);      int left_y = max(1, cur.left_y - s[hour]);      int right_x = min(n, cur.right_x + s[hour]);      int right_y = min(m, cur.right_y + s[hour]);

  area[hour] += (right_x - left_x + 1) * (right_y - left_y + 1);

  // 分裂成左、右两个子节点      q.push(Node(left_x, left_y, cur.right_x, cur.right_y));      q.push(Node(cur.left_x, cur.left_y, right_x, right_y));    }  }

// 输出每个小时的覆盖范围 for (int i = 0; i < t; ++i) { cout << area[i] << ' '; } cout << endl;

return 0