4月 08, 2008

【解題】用餐地點 - Lunch

@
台北市95學年度高中資訊學科能力競賽 - 用餐地點 (Lunch)


問題描述

  越野競賽暑期訓練營近年來報名人數大增,因此訓練營把3公頃大的訓練場隔成 m x n 個相鄰的區域,每兩個相鄰(上、下、左、右)的區域之間都有教練駐守,因此除了用餐時間外,學員不得隨意跨區接受訓練。每天早上雖然營長會將所有人分配到不同的區域進行訓練,到了午餐時,為了避免學員來回奔波,因此會選定某一區搭設臨時帳棚並將所有學員集中到這一區來用餐,當午餐時間到來時,每一區的學員就會自行往用餐區移動。根據以往的經驗,平均來講,每 0.1 秒就可以有一人從自己所在區域移動到一個相鄰的區域(換句話說,每一秒可以有 10 人次轉換至相鄰區域)。為了使所有學員能儘速到達用餐區,請寫一個程式幫營長決定應該將午餐設在哪一區。

範例:
  以下圖為例,訓練場已分割成 3 x 5 個區域,其中第(1, 1)區有5個學員、第(3, 4)區有3個學員,而第(1, 3), (2, 1), (2, 3), (2, 5), (3, 2), (3, 3)及(3, 5)區都沒有任何學員。




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

  測試檔案的第一行有兩個數字 m, n, (1 <= m, n <= 100)分別代表訓練場的區隔方式(如上圖所示),因此第 i, j 區的區域代號就是(i, j)。接下來的 m 行,每一行有 n 個整數,這 m 行中的第 i 行的第 j 個整數代表(i, j)區的學員數。每兩個整數之間都會有一個空白。


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

  請輸出能最快讓所有學員都能集中到達用餐的區域代號。輸出時,不需要輸出括號或逗點,只需要將代表該區的兩個整數輸出並以空白隔開。


輸入檔範例

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


輸出檔範例

1 2


解題思考

  首先分析題目的意思,我們可以知道,要求的結果是希望讓"所有人的移動區域數總和"為最小的最佳化題目。

  至於移動區域數的計算方式,假設現在某甲的位置在(a, b),則某甲移動到(i, j)的移動區域數就等於:|a - i| + |b - j|。

  接著,使用暴力法,計算每個區域的移動總格數,求出能得到最小值的地點,就是答案了。


參考解答(C)

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

int main(void)
{
    int m, n, x, y, fx, fy, i, j, sum, a, b, min = INT_MAX;
    int** man;

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

    if (!(in = fopen("C:/lunch/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);

    // 動態配置記憶體空間
    man = (int**)malloc(sizeof(int*) * m);
    for (i = 0; i < m; i++)
    {
        man[i] = (int*)malloc(sizeof(int) * n);

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

        printf("\n");
    }

    fclose(in);

    for (a = 1; a <= m; a++)
    {
        for (b = 1; b <= n; b++)
        {
            // 設用餐地點為 (a, b)
            sum = 0;
            for (i = 0; i < m; i++)
            {
                for (j = 0; j < n; j++)
                {
                    // 求出 (i, j) 區域的人到達 (a, b) 區域的時間
                    x = (i + 1 - a) > 0 ? (i + 1 - a) : (a - i - 1);
                    y = (j + 1 - b) > 0 ? (j + 1 - b) : (b - j - 1);

                    sum += man[i][j] * (x + y);
                }
            }

            // 求出最小值
            if (min > sum)
            {
                min = sum;
                fx = a;
                fy = b;
            }
        }
    }

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

    fprintf(out, "%d %d\n", fx, fy);
    fclose(out);

    printf("吃飯地點為 (%d, %d)\n", fx, fy);
    printf("輸出資料在 ouput.txt\n");

    system("pause");
}

0 回覆:

張貼留言