UVA 1587 Box（木箱組裝）問題詳解與貪心/排序解法

UVA 1587 Box（木箱組裝）問題詳解與貪心/排序解法

Ivan需要用6塊矩形木板組裝一個長方體箱子。每塊木板用作箱子的一個面。給定6塊木板的寬高（單位毫米），判斷能否組成一個封閉的長方體。木板可旋轉（寬高互換）。

問題建模

長方體有3組對面，每組2塊相同的矩形。設長方體三維為a ≤ b ≤ c，則6個面為：

• 2塊 a × b
• 2塊 a × c
• 2塊 b × c

輸入的6塊木板，經旋轉使w ≥ h後，必須能分成3組，每組2塊完全相同，且這3組尺寸滿足上述長方體面關係。

解法邏輯

1. 預處理：對每塊木板，令w = max(寬,高)，h = min(寬,高)，統一「長邊在前」。
2. 排序：按w降序，w相同按h降序。排序後，同尺寸木板相鄰，且最大的面（對應b×c）在前。
3. 判定條件（下標0-based）：
   • box[0] == box[1] 且 box[2] == box[3] 且 box[4] == box[5]（3組成對）
   • box[0].w == box[2].w == box[4].w（最大邊c一致）
   • box[0].h == box[2].h 且 box[2].h == box[4].h == box[4].w（中間邊b一致，且box[4]的h==w即a==b或a<b時box[4].h==box[4].w表示a==b）

代碼中Judge()函數精確實現了上述邏輯：

if (box[0].a == box[1].a && box[1].a == box[2].a && box[2].a == box[3].a)  // 前4塊長邊相同 (c)
if (box[0].b == box[1].b && box[1].b == box[4].a && box[4].a == box[5].a)  // box[0].b=box[1].b=b; box[4].a=box[5].a=b
if (box[2].b == box[3].b && box[3].b == box[4].b && box[4].b == box[5].b)  // box[2].b=box[3].b=a; box[4].b=box[5].b=a
    return 1;

C++ 參考實現（AC代碼）

#include <iostream>
#include <algorithm>
using namespace std;

struct Plate { int w, h; } p[6];

int main() {
    while (cin >> p[0].w >> p[0].h) {
        for (int i = 0; i < 6; ++i) {
            if (i) cin >> p[i].w >> p[i].h;
            if (p[i].w < p[i].h) swap(p[i].w, p[i].h); // 統一 w >= h
        }
        sort(p, p+6, [](const Plate& a, const Plate& b) {
            return a.w != b.w ? a.w > b.w : a.h > b.h;
        });
        bool ok = (p[0].w == p[1].w && p[0].h == p[1].h &&
                   p[2].w == p[3].w && p[2].h == p[3].h &&
                   p[4].w == p[5].w && p[4].h == p[5].h &&
                   p[0].w == p[2].w && p[0].w == p[4].w && // 最大邊 c 一致
                   p[0].h == p[2].h &&                      // 次大邊 b 一致
                   p[2].h == p[4].h && p[4].h == p[4].w);   // 最小邊 a 一致，且 p[4] 是正方形 (a==b) 或 a

關鍵點總結

旋轉規範化：if (w < h) swap(w,h);消除朝向差異。
排序策略：雙關鍵字降序，將同類面聚合，並使對應長方體三維c ≥ b ≥ a自然對齊到數組前段。
幾何約束轉化為數組索引關係：利用排序後的固定位置關係直接判定，避免複雜組合搜索。
邊界情況：正方體（6面全同）、兩維相等長方體（如a=b<c）均被上述邏輯覆蓋。

本題是將幾何問題離散化為「配對+排序+索引校驗」的經典案例，展示了排序在簡化組合判定中的威力。