ZeroJudge K650: 尋找蜂后 (Queen bee)

科學家發現了一種新型的蜜蜂，它們的蜂巢結構為立方體，蜂巢被蜂巢壁分割為好幾個小空間，而蜂后住在蜂巢內最大的空間中。今日為了研究這種蜜蜂，需找到蜂巢中的最大空間，以確認蜂后位置。蜂巢的長度為 Ｌ，寬度為 Ｗ，高度為 Ｈ，請你寫一個程式計算蜂巢中的最大空間為多少。

範例測資

範例輸入範例輸出
每筆測試資料為二列：
第一列有三個正整數 L、W、H（1 <= L、W、H <= 135），Ｌ、Ｗ、Ｈ 代表蜂巢的長、寬、高。
第二列共有 L＊W＊H 個字元，前 L＊W 個字元為蜂巢的第一層，接下來 L＊W 個字元為蜂巢的第二層，以此類推。每個字元可以是 0 或 1，1 代表蜂巢壁，0 代表蜂巢中的空間。		對每筆資料請輸出一列，請輸出蜂巢中的最大空間。
3 3 3
010101010001001111111101111		7
1 2 4
10000100		6
ZeroJudge K650 範例測資

以輸入範例 1 為例，則蜂巢結構如下圖所示，蜂后所在的空間為灰色區域，共有七格。

ZeroJudge K650 測資解說

解題思路

使用 BFS，但是這個 BFS 不會有遞迴的成分，將每一次的起點都存放到同一個陣列中，這樣子 BFS 中的起點迴圈就會一直跑直到沒有點為止，並且需要紀錄每一個點是否有走過。

範例程式碼－ZeroJudge K650: 尋找蜂后 (Queen bee)

#include <iostream>
#include <vector>
using namespace std;

struct pos{
    int H;
    int L;
    int W;
    bool operator<(const pos& other) const {
        if (H != other.H) return H < other.H;
        if (L != other.L) return L < other.L;
        return W < other.W;
    }
};

char bee[500][500][500] = {};
bool MAP[500][500][500] = {};
int L, W, H, ans = -999;

pos p (const int a, const int b, const int c) {
    pos tmp;
    tmp.H = a;
    tmp.L = b;
    tmp.W = c;
    return tmp;
}

void BFS(vector<pos>start, int count) {
    for (int i = 0; i<start.size(); i++) {
        const int h = start[i].H, l = start[i].L, w = start[i].W;
        if (MAP[h][l][w]) continue;
        MAP[h][l][w] = true;
        count++;
        if (h - 1 >= 0 && !MAP[h-1][l][w] && bee[h-1][l][w] == '0') {
            start.push_back(p(h-1, l, w));
        }
        if (h + 1 < H && !MAP[h+1][l][w] && bee[h+1][l][w] == '0') {
            start.push_back(p(h+1, l, w));
        }
        if (l - 1 >= 0 && !MAP[h][l-1][w] && bee[h][l-1][w] == '0') {
            start.push_back(p(h, l-1, w));
        }
        if (l + 1 < L && !MAP[h][l+1][w] && bee[h][l+1][w] == '0') {
            start.push_back(p(h, l+1, w));
        }
        if (w - 1 >= 0 && !MAP[h][l][w-1] && bee[h][l][w-1] == '0') {
            start.push_back(p(h, l, w-1));
        }
        if (w + 1 < W && !MAP[h][l][w+1] && bee[h][l][w+1] == '0') {
            start.push_back(p(h, l, w+1));
        }
    }
    ans = max(ans, count);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> L >> W >> H;
    for (int i = 0; i<H; i++) {
        for (int j = 0; j<L; j++) {
            for (int k = 0; k<W; k++) {
                cin >> bee[i][j][k];
                MAP[i][j][k] = false;
            }
        }
    }
    for (int i = 0; i<L; i++) {
        for (int j = 0; j<W; j++) {
            if (bee[0][i][j] == '0') {
                vector<pos>start;
                start.push_back(p(0, i, j));
                BFS(start, 0);
            }
        }
    }
    cout << ans << "\n";
}

//ZeroJudge K650
//Dr. SeanXD
標籤

相關文章

發佈留言