3D 停車場

題目說明

這是一題三維空間尋找最近距離的題目。與二維的平面停車場題目概念相似，只是增加一個立體維度，讓程式碼變得更加長而已，實際上概念仍只需依照題目敘述撰寫即可。

解題過程

第一步一樣是依照題意讀入資料。X 、 Y 和 Z 為整個停車場的三維空間大小，q 為查詢數量。

int X, Y, Z;
cin >> X >> Y >> Z;
int q;
cin >> q;

接著在 main 函式外開一個三維陣列用來儲存是否有車輛已經停入。

bool park[55][55][55];

對於接下來的 q 筆查詢，我們需要先讀取輸入，接著在建立一個函式來判斷與空位停車格相距多遠。

int X, Y, Z;
cin >> X >> Y >> Z;
int q;
cin >> q;

自訂函式透過獲取兩個不同的座標，並使用 abs() 函式取絕對值。

int dis(int x1, int y1, int z1, int x2, int y2, int z2) {
    return abs(x1 - x2) + abs(y1 - y2) + abs(z1 - z2);
}

接下來的 q 次查詢我們使用 while 迴圈來遍歷。在每一次運算中，我們會檢查使用者想去的位置是否有東西了。在過往二維陣列我們已經使用過兩層的巢狀迴圈，這次三維陣列即使用三層迴圈。

while (q--) {
    // 讀入車子進入點
    int x, y, z;
    cin >> x >> y >> z;
    int mx = -1, my = -1, mz = -1;
    // 遍歷整個停車場
    for (int i = 1; i <= X; i++) {
        for (int j = 1; j <= Y; j++) {
            for (int k = 1; k <= Z; k++) {
                // 如果這個車位已經被停過就跳過
                if (park[i][j][k]) continue;
                // 該車位到進入的位置的距離
                int dist = dis(i, j, k, x, y, z);
                // 目前最近的車位的距離
                int mind = dis(mx, my, mz, x, y, z);
                // 找到更適合停的位置
                if (dist < mind || mx == -1) {
                    mx = i;
                    my = j;
                    mz = k;
                }
            }
        }
    }
}

在確定車要停的位置後，我們只需要依據題目做最後的處理。先將座標軸輸出，然後陣列中停的位置更新成 True 。

park[mx][my][mz] = true;
cout << mx << " " << my << " " << mz << endl;

解題成果

#include <iostream>
using namespace std;

bool park[55][55][55];

int dis(int x1, int y1, int z1, int x2, int y2, int z2) {
    return abs(x1 - x2) + abs(y1 - y2) + abs(z1 - z2);
}

int main() {
    int X, Y, Z;
    cin >> X >> Y >> Z;
    int q;
    cin >> q;
    while (q--) {
        int x, y, z;
        cin >> x >> y >> z;
        int mx = -1, my = -1, mz = -1;
        for (int i = 1; i <= X; i++) {
            for (int j = 1; j <= Y; j++) {
                for (int k = 1; k <= Z; k++) {
                    if (park[i][j][k]) continue;
                    int dist = dis(i, j, k, x, y, z);
                    int mind = dis(mx, my, mz, x, y, z);
                    if (dist < mind || mx == -1) {
                        mx = i;
                        my = j;
                        mz = k;
                    }
                }
            }
        }
        park[mx][my][mz] = true;
        cout << mx << " " << my << " " << mz << endl;
    }
}