Griseo 的画作：颜料扩散范围 - 分支限界法求解 - 常规

Griseo 的画作：颜料扩散范围 - 分支限界法求解

Griseo 是黄金庭园的团宠小画家，最近她又开始了她的创作。

由于 Griseo 画工强大，所以她只需要在画布（视为 n*m 的二维平面，坐标起始点为 1）的某处点上一笔，颜料就会依照 Griseo 的想法无尽扩散，颜料的扩散方式是这样的：

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

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

输入

第一行包含三个整数 n 、 m 、 t ，代表画布大小（n 行 m 列）和颜料扩散时间；第二行包含 t 个整数 s[i]，代表第 i 个小时颜料扩散的距离；第三行包含两个整数 x、y 代表颜料的初始位置。

输出

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

分析

本题可以使用分支限界法求解，每个状态可以表示为颜料某时刻的覆盖范围，每次扩散后分裂成两个子状态，即左上角和右上角两个方向。

为了方便起见，可以将每个点表示为一个状态，即颜料覆盖该点的时刻，初始化为 -1。然后从起点开始扩散，将覆盖时间赋为 0。之后每次扩散时，对于每个被扩散到的点，计算左上角和右上角的状态，并进行剪枝，即如果左上角和右上角的状态都大于等于当前扩散时间，则不需要继续扩散。

最终得到的状态即为每个小时末的颜料覆盖范围。

代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

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

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

    // 初始化状态，-1 表示未覆盖
    vector<vector<int>> state(n + 1, vector<int>(m + 1, -1));

    // 使用优先队列存储需要扩散的点
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;

    // 起点初始时间为 0
    state[x][y] = 0;
    pq.push({0, {x, y}});

    // 分支限界法求解
    for (int i = 0; i < t; ++i) {
        // 每个小时扩散一次
        while (!pq.empty()) {
            int time = pq.top().first;
            int curX = pq.top().second.first;
            int curY = pq.top().second.second;
            pq.pop();

            // 剪枝：如果当前时间大于等于当前小时，则不需要继续扩散
            if (time >= i + 1) {
                continue;
            }

            // 向上扩散
            for (int j = curX - 1; j >= 1; --j) {
                if (state[j][curY] == -1) {
                    state[j][curY] = i + 1;
                    pq.push({i + 1, {j, curY}});
                }
            }

            // 向左上角和右上角扩散
            for (int j = 1; j <= s[i]; ++j) {
                // 左上角
                int newX = curX - j;
                int newY = curY - j;
                if (newX >= 1 && newY >= 1 && state[newX][newY] == -1) {
                    state[newX][newY] = i + 1;
                    pq.push({i + 1, {newX, newY}});
                }

                // 右上角
                newX = curX - j;
                newY = curY + j;
                if (newX >= 1 && newY <= m && state[newX][newY] == -1) {
                    state[newX][newY] = i + 1;
                    pq.push({i + 1, {newX, newY}});
                }
            }
        }
    }

    // 计算每个小时末的覆盖范围
    vector<int> ans(t, 0);
    for (int i = 0; i < t; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= m; ++k) {
                if (state[j][k] == i + 1) {
                    ans[i]++;
                }
            }
        }
    }

    // 输出结果
    for (int i = 0; i < t; ++i) {
        cout << ans[i] << ' ';
    }
    cout << endl;

    return 0;
}