题目描述

Bosko 和 Susko 在一个 ( A ) 行 ( B ) 列的棋盘上玩游戏。Susko 将药箱放在某个格子后，Bosko 投掷炸弹，每次炸弹后 Susko 告知药箱是否在炸弹范围内。我们需要根据这些信息，计算药箱可能的位置数量。

解题思路

1. 问题分析：

   • 每个炸弹的范围是以 ((R, S)) 为中心、边长为 ( P ) 的正方形（( P ) 为奇数，半径为 ( P/2 )）。
   • 对于每个炸弹：
     • 若 ( T=1 )，药箱必须在炸弹范围内（否则矛盾）。
     • 若 ( T=0 )，药箱必须不在炸弹范围内（否则矛盾）。
   • 最终需要统计满足所有炸弹条件的格子数量。

2. 算法思路：

   • 初始化可能位置：用二维数组 possible 标记每个格子是否可能，初始时所有格子均可能（设为 true）。
   • 过滤条件：遍历每个炸弹，根据 ( T ) 的值更新 possible：
     • ( T=1 )：仅保留在炸弹范围内的格子为可能。
     • ( T=0 )：排除炸弹范围内的格子，标记为不可能。
   • 统计结果：遍历整个棋盘，统计仍标记为可能的格子数量。

解决代码

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

int main() {
    int A, B, K;
    cin >> A >> B >> K;
    
    // 创建并初始化棋盘，周围有边界
    vector<vector<int>> board(A + 2, vector<int>(B + 2, 0));
    
    for (int _ = 0; _ < K; ++_) {
        int R, S, P, T;
        cin >> R >> S >> P >> T;
        
        if (T == 1) {
            // 处理类型1：增加概率
            for (int i = max(1, R - P / 2); i <= min(A, R + P / 2); ++i) {
                for (int j = max(1, S - P / 2); j <= min(B, S + P / 2); ++j) {
                    if (board[i][j] == 0) {
                        board[i][j] += 1;
                    } else if (board[i][j] == -1) {
                        continue;
                    } else if (board[i][j] > 0) {
                        board[i][j] += 1;
                    }
                }
            }
        } else {
            // 处理类型2：完全污染
            for (int i = max(1, R - P / 2); i <= min(A, R + P / 2); ++i) {
                for (int j = max(1, S - P / 2); j <= min(B, S + P / 2); ++j) {
                    board[i][j] = -1;
                }
            }
        }
    }
    
    // 计算最大概率和出现次数
    int max_prob = 1;
    int t = 0;
    for (int i = 1; i <= A; ++i) {
        for (int j = 1; j <= B; ++j) {
            if (board[i][j] == max_prob) {
                t += 1;
            } else if (board[i][j] > max_prob) {
                max_prob = board[i][j];
                t = 1;
            }
        }
    }
    
    cout << t << endl;
    return 0;
}

代码解释

1. 输入处理：读取棋盘大小 ( A, B ) 和炸弹数量 ( K )。
2. 初始化可能位置：possible 数组初始化为 true，表示所有格子初始均可能。
3. 处理每个炸弹：
   • 计算炸弹范围的行列边界（半径为 ( P/2 )）。
   • 遍历每个格子，根据 ( T ) 的值更新 possible：
     • ( T=1 ) 时，仅当格子在范围内时保留可能（possible[i][j] &= in_range）。
     • ( T=0 ) 时，仅当格子不在范围内时保留可能（possible[i][j] &= !in_range）。
4. 统计结果：遍历棋盘，计数仍为 true 的格子数量并输出。

复杂度分析

• 时间复杂度：( O(K \times A \times B) )，其中 ( K ) 为炸弹数量，每个炸弹需遍历 ( A \times B ) 个格子。
• 空间复杂度：( O(A \times B) )，用于存储每个格子的可能状态。