题解：P1789 【Mc生存】插火把

· · 题解

P1789 【Mc生存】插火把

算法：

本题采用简单粗暴的枚举法。对于每一个火把和萤石，都需将其影响范围内的地方进行标记。

题面最下方给出了数据范围：1 \le m+k \le 25，1 \le m \le 25，0 \le k \le 5。通过计算最坏情况下的时间复杂度：5 \times 25 + 20 \times 13 = 385，时间绰绰有余，不用担心超时。

思路听懂后，代码非常好写。

Code:

#include<bits/stdc++.h>
using namespace std;
int n,m,k,x,y,a[110][110],cnt;
int dir1[15][2]={-2,0,
                 -1,-1, -1,0, -1,1,
                 0,-2, 0,-1, 0,0, 0,1, 0,2,
                 1,-1, 1,0, 1,1,
                 2,0};
//dir1表示(x,y)的前后左右及斜方的共13位。
int dir2[30][2]={-2,-2, -2,-1, -2,0, -2,1, -2,2,
                 -1,-2, -1,-1, -1,0, -1,1, -1,2,
                  0,-2,  0,-1,  0,0,  0,1,  0,2,
                  1,-2,  1,-1,  1,0,  1,1,  1,2,
                  2,-2,  2,-1,  2,0,  2,1,  2,2};
//dir2表示(x,y)周围5*5的方阵。
int main(){
    scanf("%d%d%d",&n,&m,&k);
    while(m--){//枚举每个火把。
        scanf("%d%d",&x,&y);
        for(int i=0;i<13;i++){
            int nx=x+dir1[i][0],ny=y+dir1[i][1];
            if(nx<1 || ny<1 || nx>n || ny>n)continue;
            a[nx][ny]++;
            if(a[nx][ny]==1)cnt++;//此次被照亮，则计数器+1。
        }
    }while(k--){//枚举每个萤石。
        scanf("%d%d",&x,&y);
        for(int i=0;i<25;i++){
            int nx=x+dir2[i][0],ny=y+dir2[i][1];
            if(nx<1 || ny<1 || nx>n || ny>n)continue;
            a[nx][ny]++;
            if(a[nx][ny]==1)cnt++;//去重，防止多算。
        }
    }
    printf("%d",n*n-cnt);//总个数-被光照亮的个数。
    return 0;//好习惯。
}

有疑问及时私信哦！