【解題】積木的拼疊問題 - Bricks

台北市96學年度高中資訊學科能力競賽 - 積木的拼疊問題 (Bricks)


問題描述

　　小明和同學一起組隊參加拼疊積木比賽，比賽規則如下：

　　　1. 由各隊隊員在限定時間內到運動場的沙地上尋找小積木。
　　　2. 利用找到的小積木，每二個對應為一組，拼成正方形或長方形的大積木。
　　　3. 看看那一隊找到的小積木所組成的大積木面積最大，即可獲勝。

　　如果我們知道小明這一隊所找到小積木個數與它們的高度和長度，請你寫一個程式算出他們利用這些小積木可以拼出來的大積木的最大面積。

說明：

　　1. 每個埋在沙中的小積木寬度(W)若為一單位，則長度(L)與高度(H)為一單位的整數倍，且長度與寬度的四個邊中至少有一個邊是整齊的，不會有凹凸的狀況。小積木為實心的，沒有挖洞，而且不會是正方形或長方形，下圖所示為一部份小積木的樣子。



　　2. 若將小積木整齊的那一個邊對齊坐標軸L，則上圖小積木皆可用一串數字表示，這一串數字的個數等於小積木的長度，而每一個數字則代表其對應的高度。例如：小積木A = (1, 2, 2, 2, 2)、B = (1, 2, 1, 2, 1)、C = (2, 1, 2, 1, 2)、D = (4, 3, 2, 1)、E = (4, 1)、F = (3, 3, 1)、以及G = (2, 2, 2, 1, 1)。

　　3. 小積木是可以利用旋轉或翻轉來組成正方形或長方形的大積木的，但所組成的大積木必需是實心的，也就是小積木與小積木的接觸面必需密合，中間不能有洞產生。例如上圖中的小積木B 與C 可以組成一個3×5 的長方形大積木，而E和G 則可以組成3×4 的長方形大積木。另外，如果有二個E 就可以組成5×2的長方形大積木，而二個D 可以組成5×4 的正方形大積木了。

條件限制：

　　1. 小積木的長(L)寬(W)高(H)之範圍如下： W = 1、1 < L < 30、1 < H < 30。
　　2. 小積木的個數最多50 個，它們的樣子是可以重覆出現的。
　　3. 任何一個正方形或長方形的大積木只能由二個小積木組成，但小積木在組合時可以旋轉或翻轉。
　　4. 若找到的小積木皆無法組成大積木，請輸出0。


輸入檔格式(C:\bricks\input.txt)

　　1. 檔案第一行的數字代表小積木的個數。
　　2. 檔案第二行以後，每一行皆由一串數字組成，數字間利用空白分隔，這一串數字表示一個小積木，表示方式如說明(2)。


輸出檔格式 (C:\bricks\output.txt)

　　輸出的數字為由小積木組成的大積木的最大面積。


輸入檔範例1

5
1 2 1 2 1
2 1 2 1 2
4 3 2 1
4 3 2 1
1 3 2 1


輸出檔範例1

20


輸入檔範例2

4
4 1
1 4
1 1 1 2
4 1


輸出檔範例2

10


解題思考

　　首先，我們先想想該如何儲存輸入的每個小積木。在這裡，我選擇使用一個整數陣列來存一個積木。陣列的大小即為積木的長度(L)，而每個陣列元素，即為該列的高度(H)。

　　然後看到題目，我們還需要讓小積木適當的旋轉、組合，使之成為一個實心方塊。因此，我們需要解決的幾個問題有：

　　　1.如何判斷兩塊小積木能否組成實心方塊。
　　　2.小積木該如何旋轉。
　　　3.兩塊小積木應該怎麼組合。

　　該怎麼判斷兩塊積木能組合成題目要求的實心方塊？由於題目規定小積木皆為實心，因此我們可以直接利用兩塊積木的高度總和。假如兩塊積木的高度總和恆等，就代表兩塊積木能夠組合成實心方塊。

　　例如下面這張圖。由於左邊的兩塊積木，組合之後的高度總和皆為 3，所以可以判斷出，這兩塊積木能夠組合成一塊 3 * 3 實心方體積木。反之，右邊兩塊積木的高度則不全相等，因此得知其無法組成一塊實心方塊。



　　再來我們看到第二點。小積木的旋轉，其實就只是使之長度與高度互換。例如題目例圖的 E = (4, 1)，旋轉後即變為 E' = (2, 1, 1, 1)。



　　因為我們希望，在圖形旋轉後仍然可以用同樣的陣列表示法。也就是說，其朝下的邊必須維持整齊，且保持實心狀態。簡單來講，就是旋轉前必須確定，原圖形的高度是呈遞增或遞減的。例如題目圖形的 A、D、E、F、G；相對的，圖形 B 跟 C 則不可以旋轉。

　　關於旋轉積木，我們只需要做到這個部份。或許你還會想到需要左右顛倒。例如圖形 D = (4, 3, 2, 1) 旋轉後即成為 D' = (1, 2, 3, 4)。不過關於這個部份，我把它合併到判斷實心方塊的部份了。這只是我的作法，僅供參考，你也可以將之獨立出來。

　　最後，我們要思考，兩塊小積木應該怎麼組合？讓我們先這樣想：由於只需要靠高度總和，就可判斷兩個小積木能否組合，因此我們只需要考慮長度方向擺放的位置。

　　至於兩個積木間總共有多少排法。先設積木 A 的長度為 L_A，積木 B 的長度為 L_B，則總排法應該會有 L_A + L_B - 2 種。假如不知道為什麼，可以畫出兩個高度皆為 1 的長方體積木，自己試看看能夠排幾種。


參考解答(C++)

#include <iostream>
#include <fstream>

#define _GET_MAX_ 256

using namespace std;

bool rotate(int *, int &);
int link(int *, int, int *, int);

int main(void)
{
    ifstream in("input.txt");
    ofstream out("output.txt", ios_base::trunc);

    int **brick, *len, n, bmax = 0;

    cout << "讀入資料 . . ." << endl;
    in >> n;
    cout << n << endl;

    // 動態規劃記憶體
    brick = new int *[n];
    len = new int[n];

    // 消除這行剩下的部份
    char get[_GET_MAX_];
    in.getline(get, _GET_MAX_);

    // 進入資料讀取迴圈
    for (int i = 0; i < n; i++)
    {
        char get[_GET_MAX_];
        in.getline(get, _GET_MAX_);

        int num = 0, top = 0;
        brick[i] = new int[30];
        for (int j = 0; j < strlen(get); j++)
        {
            if (get[j] >= '0' && get[j] <= '9')
            {
                num = num * 10 + get[j] - '0';
            }
            else if (num)
            {
                brick[i][top++] = num;
                cout << num << " ";
                num = 0;
            }
        }

        if (num)
        {
            brick[i][top++] = num;
            cout << num << " ";
        }

        len[i] = top;

        cout << endl;
    }

    in.close();

    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            // 組合積木並求出面積
            int area = link(brick[i], len[i], brick[j], len[j]);

            if (!area && rotate(brick[i], len[i]))
            {
                area = link(brick[i], len[i], brick[j], len[j]);
            }

            if (!area && rotate(brick[j], len[j]))
            {
                area = link(brick[i], len[i], brick[j], len[j]);
            }

            bmax = max(bmax, area);
        }
    }

    for (int i = 0; i < n; i++) { delete [] brick[i]; }
    delete [] brick;
    delete [] len;
 
    out << bmax << endl;
    out.close();

    cout << "組合最大面積為 " << bmax << endl;
    cout << "輸出資料在 ouput.txt" << endl;

    system("pause");
}

bool rotate(int *brick, int &len)
{
    // 確認是否可以翻轉
    bool ok[2] = {true, true};
    for (int i = 1; i < len; i++)
    {
        if (ok[0] && brick[i] > brick[i - 1]) { ok[0] = false; }

        if (ok[1] && brick[i] < brick[i - 1]) { ok[1] = false; }

        if (!ok[0] && !ok[1]) { return false; }
    }

    int n = max(brick[0], brick[len - 1]);

    // 執行翻轉的動作
    int *b = new int[len];
    for (int i = 0; i < len; i++) { b[i] = brick[i]; }

    for (int i = 0; i < n; i++)
    {
        brick[i] = 0;

        for (int j = 0; j < len; j++)
        {
            if (b[j] > i) { brick[i]++; }
        }
    }

    // 更新積木長度
    len = n;

    return true;
}

int link(int *brick1, int len1, int *brick2, int len2)
{
    // 試著從各個位置組合
    for (int i = 1; i < len1 + len2; i++)
    {
        int t, s = min(len1, len2), b = max(len1, len2);

        // 判斷組合後的長度
        if (i < s)      { t = b + s - i; }
        else if (i > b) { t = i; }
        else            { t = b; }

        // 正反各測試一次
        for (int j = 0; j < 2; j++)
        {
            // 判斷是否可組合成方形
            int k, hei = 0;
            for (k = 0; k < t; k++)
            {
                int check = 0;

                // 分別加總每排的高
                if (i < len1)
                {
                    if (k < len1) { check += brick1[k]; }

                    int n = k - len1 + i;
                    if (n >= 0 && n < len2)
                    {

                        if (j)  { check += brick2[len2 - n - 1]; }
                        else    { check += brick2[n]; }
                    }
                }
                else
                {
                    int n = k + len1 - i;
                    if (n >= 0 && n < len1)
                    {
                        check += brick1[n];
                    }

                    if (k < len2)
                    {
                        if (j)  { check += brick2[len2 - k - 1]; }
                        else    { check += brick2[k]; }
                    }
                }

                // 無法組合, 跳出
                if (!hei) { hei = check; }
                else if (check != hei) { break; }
            }

            // 若成功組合則返回積木面積
            if (k == t) { return hei * t; }
        }
    }

    // 無法組合, 返回0
    return 0;
}