P1789 【Mc生存】插火把

时间限制: 1.00s    内存限制: 125.00MB

题目描述

话说有一天，linyorson 在“我的世界”中开了一个 n×n 的方阵。现在他有 m 个火把和 k 个萤石，分别放在 (x1​,y1​)∼(xm​,ym​) 和 (o1​,p1​)∼(ok​,pk​) 的位置。已知没有光并且没放东西的地方会生成怪物，请问在这个方阵中有几个点会生成怪物？

注意，在本题中火把与萤石的照明范围与原版 Minecraft（我的世界）不尽相同，请以本题中的描述为准。

火把的照亮范围是：

萤石是：

输入格式

输入共 m+k+1 行。

第一行为两个正整数 n,m 和一个非负整数 k。
第二到第 m+1 行每行两个正整数 xi​,yi​，表示各个火把的位置。
第 m+2 到第 m+k+1 行每行两个正整数 oi​,pi​，表示各个萤石的位置。

数据中可能没有萤石，但一定有火把。

输出格式

有几个点会生出怪物。

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    struct position{
        int x;
        int y;
    };
    vector<position> torch(m),fluorite(k);
    vector<vector<int>> square(n+4,vector<int>(n+4,0));
    for(int i =0;i<m;i++){
        cin>>torch[i].x>>torch[i].y;
        for(int j = 0;j<5;j++){
            int h =(5 - 2*abs(2-j))/2;
            for(int m = 2-h;m<=2+h;m++){
                square[torch[i].x+m-1][torch[i].y+j-1] = 1;
            }
        }
        
    }
    for(int i =0;i<k;i++){
        cin>>fluorite[i].x>>fluorite[i].y;
        for(int j = 0;j<5;j++){
            for(int m = 0;m<5;m++){
                square[fluorite[i].x+m-1][fluorite[i].y+j-1] = 1;
            }
        }
    }
    int monster = 0;
    for(int i = 2;i<n+2;i++){
        for(int j = 2;j<n+2;j++){
            if(square[i][j]==0){
                monster++;
            }
        }
    }
    cout<<monster;
}