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

題目描述

給定一個 n × m 的網格，每個格子 (i, j) 堆疊了高度為 h[i][j] 的積木。求這些積木構成的立體圖形的總表面積（不計算底面）。

解題思路

這是一道基礎幾何題。總表面積等於所有積木暴露在外的面的面積之和。可以從頂面、四個側面分別計算：

• 頂面：每個高度 > 0 的格子貢獻 1 面積。
• 四個方向（上下左右）：若相鄰格子高度較低，則當前格子在該方向暴露的面積為高度差；若相鄰格子不存在（邊界），則整個側面暴露，面積等於當前高度。

遍歷所有格子，累加上述貢獻即可。

代碼實現

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int T, n, m, h[55][55];

int main() {
    scanf("%d", &T);
    while (T--) {
        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] != 0) 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;
}

複雜度分析

時間複雜度 O(T * n * m)，空間複雜度 O(n * m)。n, m ≤ 50，極其輕鬆通過。

總結

本題考察對三維立體表面積的理解，關鍵在於將問題分解為六個方向的投影差。代碼簡潔，邊界處理利用 h[0][*] 和 h[*][0] 初始化為 0 即可統一邏輯。