皮皮和月亮石

题目描述

在上一话中，小智最终挑战成功，他得到了参加宝可梦联盟大赛的资格之一：灰色徽章，加上立志成为世界第一宝可梦饲育家的小刚，一行人继续着旅行。

然后，他们旅行到了月见山，要到达他们下一个目的地——华篮市，这条路是最快的捷径。他们来到一个山洞，在洞口遇到了一位名叫尼可的博士，他正在研究月亮石和宝可梦的来历，他相信宝可梦和月亮石都来自宇宙，他想探索宝可梦的奥秘。他们在另一个山洞里发现了很多皮皮，皮皮是一种妖精宝可梦，爱好和平，心地善良，她们守护着山洞里的月亮石，搬运宝石来为月亮石提供能量，然后等待月亮石发光，来提升自己的能力。

火箭队两人和他们的宝可梦猫猫也出现在了山洞里，他们为了抢走月亮石而不择手段，小智和小刚纷纷派出自己的宝可梦和他们战斗，并且在最后帮皮皮们夺回了月亮石。

尼可博士经历了这一次月亮石被抢的事情，决定要和皮皮们生活在一起，她们的幸福就是他的幸福。而小智一行人则继续旅行…...

而尼可博士则开始在山洞附近的土地种树，他想让这里变成一片森林，保护更多的宝可梦。这里的土地由于经常会有宝可梦行走，会发生一些变化...

现在假设有n \times mn×m格土地，请想像土地有虚拟的格子线，一若有某个大小为2 \times 22×2格子都还能用，那么就可以在这2 \times 22×2的格子上种一棵树。刚开始时每个格子都可以种树，接着有qq次变化，每次变化会多出一格土地不能用，请问在每次变化后都还剩多少种不同的位置可以种树。对于两种种树方式，只要左上角的格子座标不同就算不同。

输入描述

输入第一行有三個正整数n, m, qn,m,q。(2\le n,m \le 10^3 , 1\le q \le 10^52≤n,m≤103,1≤q≤105)

我们把格子上面数来第xx行，左边数来第yy列的格子座标定为(x,y)(x,y)。

接着有qq行，每行代表一次变化，包含兩個正整数x, yx,y，代表该次变化是格子(x,y)(x,y)不能使用。(1\le x \le n,1 \le y \le m1≤x≤n,1≤y≤m，每次变化的格子(x,y)(x,y)都不一样)

输出描述

每次变化都输出11行包含一个整数，该数字代表现在还有多少种位置可以种树。

样例输入 1

3 4 42 43 31 12 2

样例输出 1

4320

提示

样例解释：

对于第一次变化格子(2,4)(2,4)不能用后，能种树的位置的左上角可能座标为：(1,1),(1,2),(2,1),(2,2)(1,1),(1,2),(2,1),(2,2)。

对于第二次变化格子(3,3)(3,3)不能用后，能种树的位置的左上角可能座标为：(1,1),(1,2),(2,1)(1,1),(1,2),(2,1)。

对于第一次变化格子(1,1)(1,1)不能用后，能种树的位置的左上角可能座标为：(1,2),(2,1)(1,2),(2,1)。

对于第一次变化格子(2,4)(2,4)不能用后，已没有能种树的位置了。

思路：从点到边到中间的各点，若此点不可用了，则判断相邻的点是否不可用，若邻点都可用则少种一棵树，用最开始可种棵树（m-1）*（n-1）减每次减少的棵树即最后的结果

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int x[1010][1010]={0};int main(){int n,m,q;scanf("%d %d %d",&n,&m,&q);int sum=(n-1)*(m-1);int a,b;for(int i=0;i<q;i++){scanf("%d %d",&a,&b);if(a==1 && b==1){x[a][b]=1;if(x[a+1][b]==0 && x[a+1][b+1]==0 && x[a][b+1]==0){sum--;}}else if(a==1 && b==m){x[a][b]=1;if(x[a][b-1]==0 && x[a+1][b-1]==0 && x[a+1][b]==0){sum--;}}else if(a==n && b==1){x[a][b]=1;if(x[a-1][b]==0 && x[a-1][b+1]==0 && x[a][b+1]==0){sum--;}}else if(a==n && b==m){x[a][b]=1;if(x[a-1][b]==0 && x[a-1][b-1]==0 && x[a][b-1]==0){sum--;}}else if(a==1){x[a][b]=1;if(x[a][b-1]==0 && x[a+1][b-1]==0 && x[a+1][b]==0){sum--;}if(x[a+1][b]==0 && x[a+1][b+1]==0 && x[a][b+1]==0){sum--;}}else if(a==n){x[a][b]=1;if(x[a][b-1]==0 && x[a-1][b-1]==0 && x[a-1][b]==0){sum--;}if(x[a-1][b]==0 && x[a-1][b+1]==0 && x[a][b+1]==0){sum--;}}else if(b==1){x[a][b]=1;if(x[a-1][b]==0 && x[a-1][b+1]==0 && x[a][b+1]==0){sum--;}if(x[a+1][b]==0 && x[a+1][b+1]==0 && x[a][b+1]==0){sum--;}}else if(b==m){x[a][b]=1;if(x[a][b-1]==0 && x[a-1][b-1]==0 && x[a-1][b]==0){sum--;}if(x[a][b-1]==0 && x[a+1][b-1]==0 && x[a+1][b]==0){sum--;}}else{x[a][b]=1;if(x[a][b-1]==0 && x[a-1][b-1]==0 && x[a-1][b]==0){sum--;}if(x[a][b+1]==0 && x[a-1][b+1]==0 && x[a-1][b]==0){sum--;}if(x[a][b-1]==0 && x[a+1][b-1]==0 && x[a+1][b]==0){sum--;}if(x[a][b+1]==0 && x[a+1][b+1]==0 && x[a+1][b]==0){sum--;}}printf("%d\n",sum);}return 0;}

如果觉得《皮皮和月亮石》对你有帮助，请点赞、收藏，并留下你的观点哦！