1 条题解

  • 0
    @ 2025-5-6 4:12:52

    解题思路:

    本题要求模拟炸药在水中的爆炸过程,计算被炸到的鱼的数量。关键在于正确处理炸药的爆炸范围及鱼的位置的判定。

    关键步骤:

    1. 输入解析

      • 循环读取数据集,直到遇到终止标志 ENDOFINPUTENDOFINPUT
      • 每个数据集以 STARTSTART LL WW DD 开头,后接炸药列表和鱼群列表。
    2. 爆炸范围计算

      • 炸药下沉至深度 minmin(导火索长度, 海湾深度) 时爆炸。
      • 标记爆炸点及其上下左右前后六个相邻位置的区域。
    3. 鱼群判定

      • 遍历所有鱼的位置,检查是否位于爆炸区域内。
      • 统计被炸到的鱼的数量。

    实现细节:

    • 三维空间标记:使用三维数组 aa 记录爆炸区域,坐标范围为 0xL0 ≤ x ≤ L0yW0 ≤ y ≤ W0zD0 ≤ z ≤ D
    • 导火索处理:若导火索长度超过海湾深度,爆炸点固定在海湾底部。
    • 爆炸扩散:对每个爆炸点,将其自身及六个相邻位置标记为有效区域。

    特殊情况处理:

    • 多个炸药的爆炸区域可能重叠,不影响最终统计。
    • 所有坐标均在合法范围内,无需额外越界检查。

    C++实现:

    #include <iostream>
    #include <cstring>
    #include <vector>
    #include <sstream>
    #include <algorithm>
    #include <stdio.h>
    using namespace std;
    
    int main() {
        vector<int> results; // 存储各数据集的炸鱼结果
        string token;
        
        while (cin >> token && token != "ENDOFINPUT") {
            int L, W, D;
            cin >> L >> W >> D;
            int space[21][21][21]; // 三维爆炸标记数组
            memset(space, 0, sizeof(space));
            
            cin.ignore(); // 忽略换行符
            string bomb_line, fish_line;
            getline(cin, bomb_line);
            getline(cin, fish_line);
            
            // 处理炸药数据
            stringstream bomb_stream(bomb_line);
            string bomb;
            while (bomb_stream >> bomb) {
                for (size_t i = 0; i < bomb.size(); i++)
                    if (bomb[i] == ',') bomb[i] = ' ';
                    
                stringstream ss(bomb);
                int x, y, f;
                ss >> x >> y >> f;
                int z = min(f, D);
                
                space[x][y][z] = 1;
                if (x > 0) space[x-1][y][z] = 1;
                if (x < L) space[x+1][y][z] = 1;
                if (y > 0) space[x][y-1][z] = 1;
                if (y < W) space[x][y+1][z] = 1;
                if (z > 0) space[x][y][z-1] = 1;
                if (z < D) space[x][y][z+1] = 1;
            }
            
            // 处理鱼群数据
            int fish_count = 0;
            stringstream fish_stream(fish_line);
            string fish;
            while (fish_stream >> fish) {
                for (size_t i = 0; i < fish.size(); i++)
                    if (fish[i] == ',') fish[i] = ' ';
                    
                stringstream ss(fish);
                int x, y, z;
                ss >> x >> y >> z;
                if (space[x][y][z]) fish_count++;
            }
            
            results.push_back(fish_count);
            cin >> token; // 读取"END"
        }
        
         // 输出结果
        for (size_t i = 0; i < results.size(); i++) {
            if (results[i] > 0)
                printf("AIEE, I got %d fish, me!\n", results[i]);
            else
                puts("None of dem fish blowed up!");
        }
        
        return 0;
    }
    
    • 1

    信息

    ID
    1583
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    8
    已通过
    1
    上传者