欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年青铜组真题解析 | 汇总-CSDN博客
P9944 Comfortable Cows
【题目来源】
洛谷：[P9944 USACO21FEB] Comfortable Cows B - 洛谷
【题目描述】
Farmer John 的草地可以被看作是一个由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘）。初始时，草地上是空的。
Farmer John 将会逐一地将N NN（1 ≤ N ≤ 10 5 1\le N\le 10^51≤N≤105）头奶牛加入到草地上。第i ii头奶牛将会占据方格( x i , y i ) (x_i,y_i)(xi,yi)，不同于所有已经被其他奶牛占据的方格（0 ≤ x i , y i ≤ 1000 0\le x_i,y_i\le 10000≤xi,yi≤1000）。
一头奶牛被称为是「舒适的」，如果它水平或竖直方向上与恰好三头其他奶牛相邻。Farmer John 对他的农场上舒适的奶牛数量感兴趣。对1 … N 1\ldots N1…N中的每一个i ii，输出第i ii头奶牛加入到草地上之后舒适的奶牛的数量。
【输入】
输入的第一行包含一个整数N NN。以下N NN行每行包含两个空格分隔的整数，表示一头奶牛所在的方格坐标( x , y ) (x,y)(x,y)。输入保证所有方格的坐标是不同的。
【输出】
输出的第i ii行包含前i ii头奶牛加入到草地上之后舒适的奶牛的数量。
【输入样例】
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【解题思路】
【算法标签】
《洛谷 P9944 Comfortable Cows》 #USACO# #O2优化# #2021#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;intn,res=0,cnt=0;inta[1005][1005];intdx[4]={-1,0,1,0},dy[4]={0,1,0,-1};intmain(){cin>>n;// 输入nfor(inti=1;i<=n;i++){// 遍历n头奶牛intx,y;// 定义每头奶牛的坐标x和yintcnt1=0,cnt2=0;// 定义添加前和添加后舒适量的统计cin>>x>>y;// 输入奶头的坐标for(inti=x-1;i<=x+1;i++){// 遍历这台奶牛周围，计算添加之前的舒适量for(intj=y-1;j<=y+1;j++){intans=0;// 定义周围奶牛的数量，初始为0if(a[i][j]==1){// 如果该位置有奶牛for(intk=0;k<4;k++){// 则判断周围4个方向是否有奶牛intxx=i+dx[k];intyy=j+dy[k];if(xx<0||yy<0)continue;if(a[xx][yy]==1)ans++;// 有的话，ans自增}if(ans==3)cnt1++;// 如果ans为3，则舒适的奶牛数量加1}}}a[x][y]=1;// 添加输入的奶牛for(inti=x-1;i<=x+1;i++){// 再次遍历这台奶牛周围，计算添加之后的舒适量for(intj=y-1;j<=y+1;j++){intans=0;if(a[i][j]==1){for(intk=0;k<4;k++){intxx=i+dx[k];intyy=j+dy[k];if(xx<0||yy<0)continue;if(a[xx][yy]==1)ans++;}if(ans==3)cnt2++;// 如果ans为3，则舒适的奶牛数量加1}}}res+=cnt2-cnt1;// 计算前后的变化，并累加到ans中（有时相减会变为负数）cout<<res<<endl;// 最后打印结果}return0;}【运行结果】
8 0 1 0 1 0 0 1 1 0 1 2 1 2 1 0 2 2 0 3 1 1 3 2 2P9945 Clockwise Fence
【题目来源】
洛谷：[P9945 USACO21FEB] Clockwise Fence B - 洛谷
【题目描述】
围绕 Farmer John 最大的草地的栅栏已经损坏了，如今他终于决定要换一个新的栅栏。
不幸的是，当 Farmer John 在铺设新栅栏时，一只巨大的蜜蜂突然出现，在他的草地上追着他跑，导致最后栅栏被沿着一条相当不规则的路径铺设。栅栏可以用一个字符串表示，每个字符为N（north，北）、E（east，东）、S（south，南）、W（west，西）之一。每个字符表示一米长的一段栅栏。举例来说，如果字符串为NESW，这表示栅栏从起点开始向北延伸1 11米，然后向东延伸1 11米，然后向南延伸1 11米，然后向西延伸1 11米，回到栅栏的起点。
栅栏的结束位置与开始位置相同，而这是栅栏的路径上唯一会被到达多次的位置（从而起始位置是唯一会被再次到达的位置，在栅栏结束之时）。结果，栅栏确实围起了一个草地上连通的区域，尽管这个区域可能形状十分奇特。
Farmer John 想要知道他铺设栅栏的路径是顺时针（当按字符串表示的顺序沿着栅栏的路径行走时被围起的区域位于右侧）还是逆时针（被围起的区域位于左侧）。
【输入】
输入的第一行包含一个整数N NN（1 ≤ N ≤ 20 1\le N\le 201≤N≤20）。以下N NN行每行包含一个长度不小于4 44且不超过100 100100的字符串，表示一个栅栏的路径。
【输出】
对N NN条输入的栅栏路径的每一条，输出一行，为CW（clockwise，顺时针）或CCW（counterclockwise，逆时针）。
【输入样例】
2 NESW WSSSEENWNEESSENNNNWWWS【输出样例】
CW CCW【算法标签】
《洛谷 P9945 Clockwise Fence》 #USACO# #O2优化# #2021#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;intn,ans;string s;intd[4][4]={// 定义二维数组，E为0，W为1，S为2，N为3，每个单元格的值为方向变化后的角度变化{0,0,90,-90},{0,0,-90,90},{-90,90,0,0},{90,-90,0,0}};intmain(){cin>>n;// 输入nfor(inti=1;i<=n;i++){// for循环遍历n次询问cin>>s;// 输入字符串ss=s+s[0];// 因为最后要回到原点，所以在字符串最后加上起始字符ans=0;// 每轮询问角度统计都要归零for(inti=0;i<s.length()-1;i++){// for循环遍历s.length()-2个字符，因为要比较i与i+1intx,y;// 定义x和y坐标if(s[i]=='E')x=0;// 根据i的字符确定x坐标if(s[i]=='W')x=1;if(s[i]=='S')x=2;if(s[i]=='N')x=3;if(s[i+1]=='E')y=0;// 根据i+1的字符确定y坐标if(s[i+1]=='W')y=1;if(s[i+1]=='S')y=2;if(s[i+1]=='N')y=3;if(d[x][y])ans+=d[x][y];// 当掉转角度不为0时，加上角度的变化。}if(ans==360)cout<<"CW"<<endl;// 当为360度时，说明是顺时针转回来elseif(ans==-360)cout<<"CCW"<<endl;// 当为-360度时，说明是逆时针转回来}return0;}【运行结果】
2 NESW CW WSSSEENWNEESSENNNNWWWS CCW
)
