【解題】用餐地點 - 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");
}