题解：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:

CPP

#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;//好习惯。
}

有疑问及时私信哦！

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

文章操作

P1789 【Mc生存】插火把

算法：

Code:

相关推荐

评论

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