解题思路

1. 问题理解：我们需要计算从顶层（第1层）可以到达的所有被水淹没的立方体的体积。这些立方体必须与顶层直接或间接相连（通过相邻的面）。
2. 模型建立：可以将洞穴看作一个三维网格，其中某些立方体被水淹没。我们需要从顶层的所有被淹没的立方体开始，进行广度优先搜索（BFS）或深度优先搜索（DFS），标记所有可以到达的立方体。
3. 算法选择：使用BFS从顶层的每个被淹没的立方体出发，探索所有相邻的（上下左右前后）被淹没的立方体，并统计总数。每个立方体的体积是1立方米（1000升）。
4. 实现步骤：
   • 读取输入数据，构建三维数组表示每个立方体是否被水淹没。
   • 从顶层的每个被淹没的立方体开始，进行BFS，标记所有可达的立方体。
   • 统计所有被标记的立方体的数量，乘以1000得到总升数。

解决代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct Point {
    int z, x, y;
    Point(int z=0, int x=0, int y=0) : z(z), x(x), y(y) {}
};

const int MAX_Z = 105;
const int MAX_X = 105;
const int MAX_Y = 105;

bool grid[MAX_Z][MAX_X][MAX_Y];
bool visited[MAX_Z][MAX_X][MAX_Y];
int dir[6][3] = {{0,0,1}, {0,0,-1}, {0,1,0}, {0,-1,0}, {1,0,0}, {-1,0,0}};

void solve() {
    int N;
    cin >> N;
    for (int _ = 0; _ < N; ++_) {
        int X, Y, Z;
        cin >> X >> Y >> Z;
        
        // 初始化三维数组
        memset(grid, false, sizeof(grid));
        for (int z = 1; z <= Z; ++z) {
            int P;
            cin >> P;
            for (int __ = 0; __ < P; ++__) {
                int R, S;
                cin >> R >> S;
                grid[z][R][S] = true;
            }
        }
        
        // BFS初始化
        queue<Point> q;
        memset(visited, false, sizeof(visited));
        int total = 0;
        
        // 顶层（z=1）入队
        for (int x = 1; x <= X; ++x) {
            for (int y = 1; y <= Y; ++y) {
                if (grid[1][x][y] && !visited[1][x][y]) {
                    q.push(Point(1, x, y));
                    visited[1][x][y] = true;
                }
            }
        }
        
        // 执行BFS
        while (!q.empty()) {
            Point p = q.front();
            q.pop();
            total++;
            
            for (int d = 0; d < 6; ++d) {
                int nz = p.z + dir[d][0];
                int nx = p.x + dir[d][1];
                int ny = p.y + dir[d][2];
                
                if (nz >= 1 && nz <= Z &&
                    nx >= 1 && nx <= X &&
                    ny >= 1 && ny <= Y) {
                    
                    if (grid[nz][nx][ny] && !visited[nz][nx][ny]) {
                        visited[nz][nx][ny] = true;
                        q.push(Point(nz, nx, ny));
                    }
                }
            }
        }
        
        cout << "Je nutne vycerpat " << total * 1000 << " litru vody." << endl;
    }
}

int main() {
    solve();
    return 0;
}

代码解释

1. 输入处理：读取测试用例数量 $N$，然后逐个处理每个测试用例。
2. 三维网格初始化：创建一个三维布尔数组 grid，标记每个立方体是否被水淹没。
3. BFS初始化：从顶层（$z=1$）的所有被淹没立方体开始，初始化BFS队列和访问标记数组。
4. BFS遍历：使用队列进行广度优先搜索，探索所有与顶层相连的被淹没立方体，并统计总数。
5. 输出结果：将统计的立方体数量乘以1000（转换为升）并输出结果。

通过这种方法，可以高效地计算出需要抽干的水的体积。