HDU 5538 House Building：Minecraft 風格房屋表面積計算

HDU 5538 House Building：Minecraft 風格房屋表面積計算

你玩過《Minecraft》嗎？這款風靡全球的沙盒遊戲，其世界由無數 1×1×1 的方塊在三維地圖中構成。方塊是遊戲中結構的基本單位，種類繁多：黏土、泥土、水、木材、空氣，甚至磚塊、混凝土等建築材料皆屬此類。

圖 1：典型的 Minecraft 世界

資深玩家喵喵醬最愛在遊戲中建造宏偉宅邸。某日，他發現一片極度平坦的土地——毫無起伏，絕佳的建築基地。他決定在一塊 n×m 的平地上動工，繪製藍圖並備妥材料。一切看似順利，卻發現忘了準備裝飾關鍵的玻璃元素。如今他把藍圖交給你，請你幫忙計算需要收集多少玻璃單位。

地面劃分為 n 行 m 列，每個行列交叉處為一個 1×1 的方格，可放置方塊。為簡化問題，藍圖可表示為整數陣列 c_i,j（1≤i≤n, 1≤j≤m），代表第 i 行第 j 列方格上房屋的高度。所需玻璃單位數等於房屋的表面積（不含貼地面的底面）。

輸入格式

第一行為整數 T，代表測試案例總數。
每組測試案例第一行包含兩整數 n、m。
接下來 n 行描述藍圖陣列，第 i 行有 m 個整數 c_i,1, c_i,2, ..., c_i,m，以單一空格分隔。
限制條件：1≤T≤50，1≤n,m≤50，0≤c_i,j≤1000。

輸出格式

對每組測試案例，輸出一行，表示需收集的玻璃單位數。

範例輸入

2
3 3
1 0 0
3 1 2
1 1 0
3 3
1 0 1
0 0 0
1 0 1

範例輸出

30
20

圖 2：樣例測試案例 1 的俯視圖與側視圖

解題思路

本題本質是計算由高度矩陣定義的三維立體表面積（不含底面）。可從上、下、左、右四個方向掃描，累加相鄰兩格高度差的正值部分。具體做法：

1. 初始化答案為所有高度大於 0 的格子數（即頂面面積）。
2. 對每一格，分別與右、左、下、上四鄰居比較，若當前格高度大於鄰居，將差值加入答案（對應側面暴露面積）。
3. 邊界外視為高度 0，自動處理外側側面。

時間複雜度 O(n×m)，完全滿足 n,m≤50 的限制。

參考代碼 (C++)

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

int main() {
    int t, n, m, ans;
    int a[110][110];
    scanf("%d", &t);
    while (t--) {
        memset(a, 0, sizeof(a));
        scanf("%d%d", &n, &m);
        int k = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);
                if (a[i][j] > 0) k++; // 頂面
            }
        }
        // 四個方向掃描高度差
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                ans = a[i][j] - a[i][j+1];
                if (ans > 0) k += ans;
            }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                ans = a[i][j] - a[i][j-1];
                if (ans > 0) k += ans;
            }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                ans = a[i][j] - a[i-1][j];
                if (ans > 0) k += ans;
            }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                ans = a[i][j] - a[i+1][j];
                if (ans > 0) k += ans;
            }
        printf("%d\n", k);
    }
    return 0;
}