ZeroJudge K650: Queen Bee

Scientists have discovered a new type of bee with a beehive structure in the form of a cube. The hive is divided into several small spaces by hive walls, and the queen resides in the largest space within the hive. Today, to study these bees, you need to find the largest space within the hive to determine the queen's location. The dimensions of the hive are length L, width W, and height H. Please write a program to calculate the size of the largest space in the hive.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
Each test case consists of two lines:
The first line contains three positive integers L, W, and H (1 ≤ L, W, H ≤ 135), representing the length, width, and height of the beehive, respectively.
The second line contains L * W * H characters. The first L * W characters represent the first layer of the beehive, the next L * W characters represent the second layer, and so on. Each character can be either 0 or 1, where 1 represents a hive wall and 0 represents a space in the beehive.		For each test case, output a single line representing the size of the largest space in the beehive.
3 3 3
010101010001001111111101111		7
1 2 4
10000100		6
ZeroJudge K650 Sample Test Cases

For example, given Input Example 1, the beehive structure is as shown in the diagram below, with the queen's space highlighted in gray, totaling seven units.

ZeroJudge K650 測資解說

Thought Process

Use BFS, but ensure that it does not involve recursion. Store all starting points of each BFS iteration in the same array so that the BFS loop continues running until there are no more points left. Additionally, keep track of whether each point has been visited.

Sample Code－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
Tags

Related Posts

Comments