题B:

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1050;
int g[N][N], T, n, m;
int l[N][N], r[N][N], u[N][N], d[N][N];
int count(int a, int b) {
    int x = min(a, b / 2), y = min(a/2,b);
    if(x < 2) x = 1;
    if(y < 2) y = 1;
    return x + y - 2;
}
int main() {
    scanf("%d", &T);
    for(int C = 1; C <= T; ++C) {
        scanf("%d %d", &n, &m);
        memset(d, 0, sizeof d);
        memset(r, 0, sizeof r);
        for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) scanf("%d", &g[i][j]);
        for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j)
        {
            if(g[i][j] == 1) l[i][j] = l[i][j-1] + 1, u[i][j] = u[i-1][j] + 1;
            else l[i][j] = u[i][j] = 0;
        }
        for(int i = n; i; --i) for(int j = m; j; --j)
        {
            if(g[i][j] == 1) r[i][j] = r[i][j+1] + 1, d[i][j] = d[i+1][j] + 1;
            else r[i][j] = d[i][j] = 0;
        }
        long long res = 0;
        for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j)
        {
            int ll = l[i][j], uu = u[i][j], rr = r[i][j], dd = d[i][j];
            res += count(ll, uu) + count(ll, dd) + count(rr, dd) + count(rr, uu);
        }
        printf("Case #%d: %lld\n", C, res);
    }
}

题C

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;
using ll = long long;
const int N = 350;
int g[N][N], T, n, m;
bool st[N][N];

struct gift{
    int h, x, y;
    gift(int hh, int xx, int yy): h(hh), x(xx), y(yy){}
    bool operator<(const gift& tt) const
        { return h < tt.h; }
};

ll dij() {
    static const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
    priority_queue<gift> q;
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) q.push(gift(g[i][j], i, j));
    memset(st, 0, sizeof st);
    long long res = 0;
    while(!q.empty()) {
        int x = q.top().x, y = q.top().y;
        q.pop();
        if(st[x][y]) continue;
        st[x][y] = true;
        for(int i = 0; i < 4; ++i) {
            int u = x + dx[i], v = y + dy[i];
            if(u == 0 || v == 0 || u > n || v > m) continue;
            if(g[u][v] >= g[x][y] - 1) continue;
            res += g[x][y] - 1 - g[u][v];
            g[u][v] = g[x][y] - 1;
            q.push(gift(g[u][v], u, v));
        }
    }
    return res;
}

int main() {
    scanf("%d", &T);
    for(int C = 1; C <= T; ++C) {
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) scanf("%d", &g[i][j]);
        printf("Case #%d: %lld\n", C, dij());
    }
}

题D
…这个就不看了
稍后研究一下前面的给凡人的题目.
ref:
senako