Griseo 的画作：使用分枝限界法求解颜料扩散范围

题目描述

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

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

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

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

输入

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

输出

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

题目分析

本题可以使用搜索算法来解决，每次搜索到一个点时，将该点的值更新为当前时间，然后分别向左上和右上搜索，并更新这两个点的值为当前时间加上 s[i]。搜索过程中，如果搜到的点已经被更新过，或者超出了画布边界，则直接跳过。

在搜索过程中，可以使用优先队列（堆）来优化搜索顺序，每次取出覆盖时间最早的点进行搜索。当堆为空时，说明所有点都已经搜索完毕，可以结束搜索。

代码实现

代码中使用了一个结构体 Point 来存储每个点的坐标和覆盖时间，使用了一个数组 visited 来记录每个点是否已经被搜索过。

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

using namespace std;

struct Point {
    int x, y, time;
};

bool operator<(const Point& a, const Point& b) {
    return a.time > b.time;
}

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;

    vector<vector<int>> visited(n + 1, vector<int>(m + 1, -1));
    priority_queue<Point> pq;
    pq.push({x, y, 0});
    visited[x][y] = 0;

    vector<int> result(t, 0);
    for (int i = 0; i < t; ++i) {
        while (!pq.empty() && pq.top().time <= i) {
            Point cur = pq.top();
            pq.pop();

            // 向上扩散
            for (int j = cur.y + 1; j <= cur.y + s[i]; ++j) {
                if (j <= n && visited[cur.x][j] == -1) {
                    visited[cur.x][j] = i + 1;
                    pq.push({cur.x, j, i + 1});
                }
            }

            // 向左上和右上扩散
            if (cur.x - s[i] >= 1 && cur.y - s[i] >= 1) {
                if (visited[cur.x - s[i]][cur.y - s[i]] == -1) {
                    visited[cur.x - s[i]][cur.y - s[i]] = i + 1 + s[i];
                    pq.push({cur.x - s[i], cur.y - s[i], i + 1 + s[i]});
                }
            }
            if (cur.x + s[i] <= n && cur.y - s[i] >= 1) {
                if (visited[cur.x + s[i]][cur.y - s[i]] == -1) {
                    visited[cur.x + s[i]][cur.y - s[i]] = i + 1 + s[i];
                    pq.push({cur.x + s[i], cur.y - s[i], i + 1 + s[i]});
                }
            }
        }

        // 计算覆盖范围
        int count = 0;
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= m; ++k) {
                if (visited[j][k] <= i + 1) {
                    ++count;
                }
            }
        }
        result[i] = count;
    }

    for (int i = 0; i < t; ++i) {
        cout << result[i] << ' ';
    }
    cout << endl;

    return 0;
}

时间复杂度

由于最坏情况下每个点都需要被搜索一次，时间复杂度为 O(nmlog(nm))。空间复杂度为 O(nm)。