街道最短路徑問題

版權聲明：您好，轉載請留下本人部落格的位址，謝謝 https://blog.csdn.net/hongbochen1223/article/details/48398897

描述：

一個街區有很多住戶，街區的街道隻能為東西、南北兩種方向。住戶隻可以沿着街道行走。各個街道之間的間隔相等。用(x,y)來表示住戶坐在的街區。例如（4,20），表示使用者在東西方向第4個街道，南北方向第20個街道。現在要建一個郵局，使得各個住戶到郵局的距離之和最少。求現在這個郵局應該建在那個地方使得所有住戶距離之和最小；

輸入：

第一行一個整數n<20，表示有n組測試資料，下面是n組資料;

每組第一行一個整數m<20,表示本組有m個住戶，下面的m行每行有兩個整數(0,100)，表示某個使用者所在街區的坐标．m行後是新一組的資料；

輸出

每組資料輸出到郵局最小的距離和，回車結束；

樣例輸入

2

3

1 1

2 1

1 2

5

2 9

5 20

11 9

1 20

樣例輸出

44

代碼實作

/*
 * main.c
 *
 *  Created on: 2015年9月12日
 *      Author: bobo
 */

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

/* 交換兩個數字　*/
void swap(float *a, float *b) {
    float temp = *a;
    *a = *b;
    *b = temp;
}

/* 最簡單的排序　*/
void sort(int sum, float zuis[]) {
    int m, n;
    for (m = 0; m < sum - 1; m++)
        for (n = m + 1; n < sum; n++)
            if (zuis[n] > zuis[m])
                swap(&zuis[m], &zuis[n]);
}

/* 測試輸出　*/
void print(int sum, float zuis[]) {
    int m;
    for (m = 0; m < sum; m++)
        printf("%.1f ", zuis[m]);

    printf("\n");
}

int main() {
    /* 樣例的個數 */
    int size;

    scanf("%d", &size);

    while (size--) {
        /* 有幾乎人家 */
        int sum;

        /* 總長度 */
        int length = 0;

        int i;

        scanf("%d", &sum);

        int xs[sum];
        int ys[sum];

        for (i = 0; i < sum; i++)
            scanf("%d%d", &xs[i], &ys[i]);

        /* 儲存郵局的x和y */
        int yx, yy;

        sort(sum, xs);
        sort(sum, ys);

        /* 中間的數值 */
        int temp;

        if (sum % 2 == 0) {
            temp = sum / 2;
            yx = (xs[temp - 1] + xs[temp]) / 2;
            yy = (ys[temp - 1] + ys[temp]) / 2;
        } else {
            temp = (sum + 1) / 2;

            yx = xs[temp - 1];
            yy = ys[temp - 1];
        }

        for (i = 0; i < sum; i++)
            length += (abs(yx - xs[i]) + abs(yy - ys[i]));

        printf("%d\n", length);
    }

    return 0;
}
           

運作結果：

思路整理

該題目主要是為了求取數的中位數．