【解題】最大矩形 - Area

台北市95學年度高中資訊學科能力競賽 - 最大矩形 (Area)


問題描述

　　在一個 M x N 的區域內，散落了許多不同的障礙物，我們想要知道的是，在這個 M x N 的區域內，最大的矩形空地面積是多少？倘若我們用 0 與 1 表示這個區域內的空地狀況：0 代表這個子區域已被障礙物覆蓋，1 代表這個子區域仍為空地，我們假設每一個 0 或 1 所代表的子區域面積為 1，那麼在下面這個例子中(M = 4，N = 5)，最大的矩形空地為陰影所覆蓋的區域，其面積為 8。

　　　0 0 1 1 0
　　　0 1 1 1 1
　　　0 1 1 1 1
　　　0 0 1 0 0

　　在本題中，請依據輸入輸出的規定，針對輸入的地圖，輸出其最大的矩形空地面積。


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

　　輸入檔第一行有兩個整數，依序為 M 和 N, M ≦ 200, N ≦ 200；接下來的 M 行中，每一行有 N 個 0 或 1 的數字。這 N 個數字彼此間用一個空白隔開。


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

　　請將最大矩形空地面積寫出至輸出檔。


輸入檔範例

4 5
0 0 1 1 0
0 1 1 1 1
0 1 1 1 1
0 0 1 0 0


輸出檔範例

8


解題思考

　　題目要求我們求出"內部全是 1"最大矩形，我們就直觀的作吧。

　　首先，使用程式在儲存輸入資料的二維陣列中，用兩層迴圈(i, j)去找一個空地(即變數值為 1)為起始點。接下來的問題，就是如何尋找、並判斷矩形的大小。

　　在這裡，我在剛剛的兩層迴圈之中，再用了第三四層迴圈(x, y)。先由 x = 0 開始，得到從 i 開始最後一個連續空地的位置(y + j)，並以 x + 1 * y + 1 (因為(x, y)座標都是以 0 開始)計算矩形大小。除此之外，還需要一個變數(方便說明，下面以 y' 表示)，把這個位置記錄下來。

　　當 x = 1 時，y 就不會超過剛剛所存變數的位置。假如到這個位置之前，找到最後一個連續的空地位置(即在 y < y' 時就遇到 0)，則將 y' 更新為當前位置。並且，別忘了，在 x 遞增前，計算出這個矩形的大小。以此類推到 x = n 為最後一個連續空地。

　　或許有點難懂，這裡我們以範例輸入為例，假設我們以(3, 0)(題目以向下為x軸正向，向右為y軸正向)作為抓取矩形的起點：



　　上圖中的標上紅色的部份，是每一次計算矩形大小時抓取的範圍。標上綠色的部份，是停止抓取的分界。可以注意到，由於在第一張圖中的(0, 4)為0，因此在之後的(x, y)中，y都不會大於等於4。

　　這麼做的目的是什麼呢？假設現在在第二張圖中，我們將(1, 4)也納入判斷矩形的範圍。由於(0, 4)之值為0，因此在以(3, 0)為起點時，y大於等於4的情況下都不可得出一個矩形的。這麼做的目的就在排除這已知的情況。

　　只要這樣做下去，就能夠得出以某一點為起點的情況中，各種可能矩形面積大小。只要把每個能夠當成起點的部份(空地，即值為1)得出的面積大小做比較，自然就能夠得出最大面積了。


參考解答(C)

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int i, j, m, n, x, y, e, max = 0;
    int **area;

    // 宣告檔案串流
    FILE *in,*out=fopen("C:/area/output.txt","w+");

    if (!(in=fopen("C:/area/input.txt","r")))
    {
        printf("找不到 input.txt\n");
        system("pause");
        exit(1);
    }

    printf("讀入資料 . . .\n");
    fscanf(in, "%d %d", &m, &n);
    printf("%d %d\n", m, n);

    // 動態配置記憶體空間
    area = (int**)malloc(sizeof(int*) * m);

    for (i = 0; i < m; i++)
    {
        area[i] = (int*)malloc(sizeof(int) * n);

        for (j = 0; j < n; j++)
        {
            fscanf(in, "%d", &area[i][j]);
            printf("%d ", area[i][j]);
        }

        printf("\n");
    }

    fclose(in);

    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
        {
            // 若 (i, j) 為 1 時
            if (area[i][j])
            {
                e = 0;
                for (x = 0; x < m - i; x++)
                {
                    for (y = 0; y < n - j - e; y++)
                    {
                        if (!area[x + i][y + j])
                        {
                            // (n - j - e) 為矩形最大寬度
                            e = n - j - y;
                            break;
                        }

                        // 計算最大值
                        max = max > (x + 1) * (y + 1) ? max : (x + 1) * (y + 1);
                    }
                }
            }
        }
    }

    // 釋放記憶體空間
    for (i = 0; i < m; i++) { free(area[i]); }
    free(area);

    fprintf(out, "%d", max);
    fclose(out);

    printf("最大矩形面積為 %d\n", max);
    printf("輸出資料在 ouput.txt\n");

    system("pause");
}