HDU 5538 House Building：積木表面積計算

題意

給定 n×m 網格，每格 h[i][j] 表示堆疊積木高度。求總表面積（不含底面）。

解法：逐格貢獻法

每個非零格子貢獻：

• 頂面：+1
• 四側面：與鄰格高度差（僅當高於鄰格時）max(0, h[i][j] - h[ni][nj])

邊界外視為高度 0。雙重循環累加即可，O(nm)。

代碼

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int h[55][55];
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        memset(h, 0, sizeof(h));
        for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d", &h[i][j]);
        int ans = 0;
        for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (h[i][j]) {
            ans++; // 頂面
            if (h[i][j] > h[i-1][j]) ans += h[i][j] - h[i-1][j];
            if (h[i][j] > h[i+1][j]) ans += h[i][j] - h[i+1][j];
            if (h[i][j] > h[i][j-1]) ans += h[i][j] - h[i][j-1];
            if (h[i][j] > h[i][j+1]) ans += h[i][j] - h[i][j+1];
        }
        printf("%d\n", ans);
    }
    return 0;
}