思路

每个格子的标记值等于到所有僵尸的切比雪夫距离的最小值。

标记值为 $Q$ 的格子数等于距离在 $Q$ 及以内的格子数减去距离在 $Q-1$ 及以内的格子数。

距离在 $d$ 及以内的格子数等于所有僵尸在切比雪夫距离 $d$ 内覆盖区域的并集面积。

对于僵尸 $(r,c)$，距离在 $d$ 及以内的区域是矩形，行范围 $[\max(1, r-d), \min(N, r+d)]$，列范围 $[\max(1, c-d), \min(M, c+d)]$。

时间复杂度 $O(K^2 \log K)$，$K \le 2000$。

注：切比雪夫距离是一种度量空间中两点距离的方法。在二维平面网格上，点 $(x_1, y_1)$ 和点 $(x_2, y_2)$ 的切比雪夫距离为 $\max(\vert x_1 - x_2\vert, \vert y_1 - y_2\vert)$。

在本题中，僵尸向 $8$ 个方向等速扩散，每个格子的标记值就是该格子到最近僵尸的切比雪夫距离。

有的人可能会计算成曼哈顿距离。但是僵尸可以斜着走，比如从 $(0,0)$ 到 $(1,1)$，切比雪夫距离 $= \max(\vert 1-0\vert, \vert 1-0\vert) = 1$，而曼哈顿距离 $= \vert 1-0\vert + \vert 1-0\vert = 2$。但实际只需要 $1$ 步（斜着走），所以切比雪夫距离正确。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m;
vector<pair<int, int>> z;

//计算距离 ≤ d 的格子总数
ll cal(int d){
    if(d < 0)return 0;
 
    //存储每个僵尸的覆盖矩形
    vector<array<int, 4>> a;
    for(auto [r, c] : z){
        int t = max(1, r - d);
        int b = min(n, (ll)r + d);
        int l = max(1, c - d);
        int rr = min(m, (ll)c + d);
        if(t <= b && l <= rr)a.push_back({t, b, l, rr});
    }
    if(a.empty())return 0;
   
    //收集所有y坐标用于扫描线
    vector<int> ys = {1, (int)n + 1};
    for(auto [t, b, l, rr] : a){
        ys.push_back(t);
        ys.push_back(b + 1);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    ll ans = 0;

    //扫描每个y区间
    for(size_t i = 0; i + 1 < ys.size(); ++i){
        int yl = ys[i], yr = ys[i + 1] - 1;
        if(yl > yr)continue;

        //收集当前y区间内的x区间
        vector<pair<int, int>> seg;
        for(auto [t, b, l, rr] : a)
            if(t <= yr && b >= yl)seg.emplace_back(l, rr);
        if(seg.empty())continue;

        //合并x区间
        sort(seg.begin(), seg.end());
        int L = seg[0].first, R = seg[0].second;
        ll cov = 0;
        for(size_t j = 1; j < seg.size(); j++){
            if(seg[j].first <= R + 1)R = max(R, seg[j].second);
            else{
                cov += R - L + 1;
                L = seg[j].first, R = seg[j].second;
            }
        }
        cov += R - L + 1;
        ans += cov * (yr - yl + 1);
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int k, q;
    cin >> n >> m >> k;
    z.resize(k);
    for(int i = 0; i < k; i++)
        cin >> z[i].first >> z[i].second;
    cin >> q;
    cout << (q == 0 ? cal(0) : cal(q) - cal(q - 1)) << endl;
    return 0;
}