【深基5.习8】Mc生存-插火把

解题思路

用布尔网格记录亮区。火把覆盖与中心曼哈顿距离不超过 2 的格子，萤石覆盖横纵距离都不超过 2 的格子。标记后统计未亮格子。

正确性说明

两种距离条件分别与题给菱形、正方形覆盖图一致；标记取并集，未标记格子恰好没有任何光源覆盖。

易错点

光源本身也亮；靠近边缘时跳过越界格子；重叠只标记一次。

复杂度

时间 O(n²+m+k)，每光源最多检查 25 格；空间 O(n²)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<bool>> light(n + 1, vector<bool>(n + 1));
    for (int t = 0; t < m + k; t++) {
        int x, y;
        cin >> x >> y;
        for (int dx = -2; dx <= 2; dx++)
            for (int dy = -2; dy <= 2; dy++) {
                if (t < m && abs(dx) + abs(dy) > 2)
                    continue;
                int a = x + dx, b = y + dy;
                if (a >= 1 && a <= n && b >= 1 && b <= n)
                    light[a][b] = true;
            }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (!light[i][j])
                ans++;
    cout << ans << "\n";
    return 0;
}