打卡信奥刷题（3124）用C++实现信奥题 P7411 [USACO21FEB] Comfortable Cows S

P7411 [USACO21FEB] Comfortable Cows S题目描述Farmer Nhoj 的草地可以被看作是一个由正方形方格组成的巨大的二维方阵想象一个巨大的棋盘。初始时草地上是空的。Farmer Nhoj 将会逐一地将NNN1≤N≤1051\le N\le 10^51≤N≤105头奶牛加入到草地上。第iii头奶牛将会占据方格(xi,yi)(x_i,y_i)(xi​,yi​)不同于所有已经被其他奶牛占据的方格0≤xi,yi≤10000\le x_i,y_i\le 10000≤xi​,yi​≤1000。一头奶牛被称为是「舒适的」如果它水平或竖直方向上与恰好三头其他奶牛相邻。然而太舒适的奶牛往往产奶量落后所以 Farmer Nhoj 想要额外加入一些奶牛直到没有奶牛包括新加入的奶牛是舒适的。注意加入的奶牛的xxx和yyy坐标并不一定需要在范围0…10000 \ldots 10000…1000内。对于1…N1 \ldots N1…N中的每个iii输出当初始时草地上有奶牛1…i1\ldots i1…i时Farmer Nhoj 为使得没有奶牛舒适需要加入的奶牛的最小数量。输入格式输入的第一行包含一个整数NNN。以下NNN行每行包含两个空格分隔的整数表示一头奶牛所在的方格坐标(x,y)(x,y)(x,y)。输出格式输出NNN行对于1…N1 \ldots N1…N中的每个iii输出一行为 Farmer Nhoj 需要加入的奶牛数量。输入输出样例 #1输入 #19 0 1 1 0 1 1 1 2 2 1 2 2 3 1 3 2 4 1输出 #10 0 0 1 0 0 1 2 4说明/提示对于i4i4i4Farmer Nhoj 需要在(2,1)(2,1)(2,1)加入一头奶牛使得位于(1,1)(1,1)(1,1)的奶牛不再舒适。对于i9i9i9Farmer Nhoj 的最优方案是在(2,0)(2,0)(2,0)、(3,0)(3,0)(3,0)、(2,−1)(2,-1)(2,−1)和(2,3)(2,3)(2,3)加入奶牛。供题Benjamin QiC实现#includeiostream#includequeue#defineN10010usingnamespacestd;intre(){intp0;charigetchar();while(i0||i9)igetchar();while(i0i9)pp*10i-0,igetchar();returnp;}intn,m,cnt;intmap[N][N];constintdx[]{0,0,0,1,-1};constintdy[]{0,1,-1,0,0};voiddfs(intx,inty){intflag0;intt_x,t_y;if(!map[x][y])return;//牛都不是for(inti1;i4;i){intxxxdx[i];intyyydy[i];if(map[xx][yy])flag;elset_xxx,t_yyy;}if(flag!3)return;//牛不舒适不用加点else{map[t_x][t_y]1;cnt;//第一种影响for(inti0;i4;i)//0是该点dfs(t_xdx[i],t_ydy[i]);}}intmain(){nre();while(n--){intx,y;xre()1000;yre()1000;//防止数组超界if(map[x][y])cnt--;//第二种影响map[x][y]1;for(inti0;i4;i){intxxxdx[i];intyyydy[i];dfs(xx,yy);}printf(%d\n,cnt);}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容