题解 | #毒苯#

离线+优先队列优化 BFS

考虑暴力。

对于每次查询，将第一行放入队列中，然后逐步向外拓展。

时间复杂度 。

分析可得，毒的强度越强，能杀死的苯就越多。

那么可以考虑将所有的查询存下来，从小到大排序。

然后用一个优先队列（小根堆）存被污染的苯，初始值为第一行。

随后开始遍历所有查询，对于每个查询进行 bfs。

此时的 bfs 不再是从头开始，而是接着上次的 bfs 继续搜索，直到搜索到当前的苯生命值大于毒的强度。

#include <bits/stdc++.h>
using namespace std;
struct query
{
    int x, i;
    bool operator<(const query &b) const
    {
        return x < b.x;
    }
};
struct node
{
    int x, y, val;
    node() {}
    node(int x, int y, int k) : x(x), y(y), val(k) {}
    bool operator<(const node &b) const
    {
        return val > b.val;
    }
};
void _()
{
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> a(n + 7, vector<int>(m + 7)), in(n + 7, vector<int>(m + 7));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
  
    vector<query> ask(q);
    for (int i = 0; i < q; i++)
    {
        cin >> ask[i].x;
        ask[i].i = i;
    }
    sort(ask.begin(), ask.end());

    array<int, 4> dx = {0, 0, 1, -1},
                  dy = {1, -1, 0, 0};
    priority_queue<node> h;

    for (int i = 1; i <= m; i++)
    {
        h.push(node(1, i, a[1][i]));
        in[1][i] = 1;
    }
    int sum = 0;
    vector<int> ans(q);
  
    for (int qwq = 0; qwq < q; qwq++)
    {
        while (h.size())
        {
            auto [x, y, k] = h.top();

            if (k > ask[qwq].x)
                break;

            h.pop(), sum++;

            for (int i = 0; i < 4; i++)
            {
                int xx = x + dx[i], yy = y + dy[i];

                if (xx < 1 || xx > n || yy < 1 || yy > m || in[xx][yy])
                    continue;

                h.push(node(xx, yy, a[xx][yy]));
                in[xx][yy] = 1;
            }
        }
        ans[ask[qwq].i] = sum;
    }
    for (auto i : ans)
        cout << i << '\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        _();
    return 0;
}