[USACO 2021.02 Feb]Problem 2. Comfortable Cows-阿里云开发者社区

[USACO 2021.02 Feb]Problem 2. Comfortable Cows

2023-07-27 59

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： [USACO 2021.02 Feb]Problem 2. Comfortable Cows

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 头奶牛加入到草地上之后舒适的奶牛的数量。

输入样例：

0 1

1 0

1 1

1 2

2 1

2 2

3 1

3 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. }