Farmer John 的草地可以被看作是一个由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘）。初始时，草地上是空的。
Farmer John 将会逐一地将N（1≤N≤10^5）头奶牛加入到草地上。第 i 头奶牛将会占据方格 (xi,yi)，不同于所有已经被其他奶牛占据的方格（0≤xi,yi≤1000）。
一头奶牛被称为是「舒适的」，如果它水平或竖直方向上与恰好三头其他奶牛相邻。Farmer John 对他的农场上舒适的奶牛数量感兴趣。对 1......N 中的每一个 i，输出第 i 头奶牛加入到草地上之后舒适的奶牛的数量。
输入格式（从终端 / 标准输入读入）：
输入的第一行包含一个整数N。以下N行每行包含两个空格分隔的整数，表示一头奶牛所在的方格坐标(xi,yi)。输入保证所有方格的坐标是不同的。
输出格式（输出至终端 / 标准输出）：
输出的第 i 行包含前 i 头奶牛加入到草地上之后舒适的奶牛的数量。
输入样例：
8
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2
输出样例：
0
0
0
1
0
0
1
2
在前四头奶牛加入之后，位于 (1,1) 的奶牛是舒适的。
在前七头奶牛加入之后，位于 (2,1) 的奶牛是舒适的。
在前八头奶牛加入之后，位于 (2,1) 和 (2,2) 的奶牛是舒适的。
测试点性质：
测试点 1-4 满足N<=400。
测试点 5-12 没有额外限制。
供题：Benjamin Qi
1. #include <iostream> 2. #include <cstdio> 3. using namespace std; 4. int n,map[1005][1005],x,y,ans=0; 5. int xx[5]={-1,1,0,0,0}; 6. int yy[5]={0,0,-1,1,0}; 7. bool check(int x,int y){//判断该点上的奶牛否舒适 8. if(x<0||x>=n||y<0||y>=n||map[x][y]==0) 9. return false; 10. int tj=0; 11. for(int i=0;i<4;i++){//刨除自身 12. int tx=x+xx[i]; 13. int ty=y+yy[i]; 14. if(tx>=0&&tx<n&&ty>=0&&ty<n) 15. tj+=map[tx][ty]; 16. } 17. return tj==3; 18. } 19. int cal(int x,int y){ 20. int t1,t2; 21. t1=t2=0; 22. //每放一个奶牛只影响周边及自身5个点 23. for(int i=0;i<5;i++)//统计放奶牛前5个点的舒适度 24. t1+=check(x+xx[i],y+yy[i]); 25. map[x][y]=1; 26. for(int i=0;i<5;i++)//统计放奶牛后5个点的舒适度 27. t2+=check(x+xx[i],y+yy[i]); 28. return t2-t1;//舒适度增加量 29. } 30. int main() 31. { 32. cin>>n; 33. for(int i=1;i<=n;i++){ 34. cin>>x>>y; 35. ans+=cal(x,y); 36. cout<<ans<<endl; 37. } 38. return 0; 39. }
