[BZOJ2548][Ctsc2002]灭鼠行动（大模拟）

2019-11-06 06:29:41

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

又是一道大模拟。。。需要注意的几个地方： 1、一个时刻x+时间单位x~y操作的顺序是：时刻x老鼠繁殖、时刻x放武器、判断是否发生鼠疫、时间单位x~y老鼠移动。 2、只有某一个点上有且仅有两只老鼠并且满足性别互异、均成年、不在上一次繁殖期间或者昏迷状态下才可以繁殖。 3、某一次繁殖结束之后（等待+繁殖+休息），如果两只老鼠又进行了一次操作（走一步或者转一下方向），并且又同时到了同一个点上，那么它们可以接着繁殖。 4、在昏迷过程中，所有的生理活动都被暂停，包括：年龄增长、繁殖或休息的时间。 5、在繁殖过程中（等待+繁殖+休息）都不能移动。

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;int n,m,L,R,P,limit,T,now;bool plague;struct RAT{ // 当前位置 int x,y; // 朝向 0 上 1 右 2 下 3 左 int dir; // 性别 0 雄性 1 雌性 int sex; // 年龄 int age; // 还需要再等待re时间才能恢复生理活动 int re; // 第几次遇到两边都有路的情况 int cnt; // 还需要再等待multi时间才能生出小老鼠，若multi=-1则并没有进行繁殖 int multi; // 还需要再等待move时间才能运动（繁殖之后），若move=-1说明并不是繁殖刚结束，可以接着繁殖 int move; // 是否已经死亡 1 死亡 bool dead;}rat[405],bag[405];struct GUN{ // 武器的类型 1 强力炸弹 2 神秘射线 3 定时炸弹 4 生物炸弹 int type; // 放置的时间 int t; // 放置的位置 int x,y; bool Operator < (const GUN &a) const { return t<a.t; }}gun[105];// 目前的老鼠总数int tot;// 下水道中每一个位置的结构 int loc[55][55];// 方向转化为二进制数int trans[4]={1,2,4,8};// 四种走法int dx[4]={-1,0,1,0};int dy[4]={0,1,0,-1}; // 判断每一个位置是否被当前的强力炸弹攻击到 bool vis[55][55]; // 当前时刻下水道中每一个位置存在的老鼠集合、大小int s[55][55][405],size[55][55];void Multi(){ memset(size,0,sizeof(size)); // 统计每一个点有多少只老鼠 for (int i=1;i<=tot;++i) { int x=rat[i].x,y=rat[i].y; s[x][y][++size[x][y]]=i; } for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) // 如果某一个点只有两只老鼠 if (size[i][j]==2) { int id=s[i][j][1],jd=s[i][j][2]; // 性别互异 if (rat[id].sex==rat[jd].sex) continue; // 成年 if (rat[id].age<5||rat[jd].age<5) continue; // 如果未恢复生理活动 if (rat[id].re||rat[jd].re) continue; // 如果在生育过程中 if (rat[id].multi!=-1||rat[jd].multi!=-1) continue; // 如果在休息过程中 if (rat[id].move!=-1||rat[jd].move!=-1) continue; rat[id].multi=rat[jd].multi=2; } for (int i=1;i<=tot;++i) { // 如果未恢复生理活动或者在休息过程中 if (rat[i].re||rat[i].move!=-1) continue; // 如果现在要生小老鼠 if (!rat[i].multi) { rat[i].move=1;rat[i].multi=-1; // 两个性别只处理一个 if (rat[i].sex) continue; int x=rat[i].x,y=rat[i].y; for (int j=0;j<4;++j) if (loc[x][y]&trans[j]) { ++tot; rat[tot].x=x,rat[tot].y=y; rat[tot].dir=j; // 南北是雄性，东西是雌性 if (j&1) rat[tot].sex=1; else rat[tot].sex=0; rat[tot].age=rat[tot].cnt=rat[tot].dead=rat[tot].re=0; rat[tot].multi=rat[tot].move=-1; } } }}int Dis(RAT a,GUN b){ return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}void Attack(GUN now){ switch (now.type) { // 强力炸弹 case 1: { memset(vis,0,sizeof(vis)); int x,y,cnt; x=now.x,y=now.y;cnt=0;vis[x][y]=1; while ((loc[x][y]&1)&&cnt<L) { --x;++cnt; vis[x][y]=1; } x=now.x,y=now.y;cnt=0; while ((loc[x][y]&2)&&cnt<L) { ++y;++cnt; vis[x][y]=1; } x=now.x,y=now.y;cnt=0; while ((loc[x][y]&4)&&cnt<L) { ++x;++cnt; vis[x][y]=1; } x=now.x,y=now.y;cnt=0; while ((loc[x][y]&8)&&cnt<L) { --y;++cnt; vis[x][y]=1; } for (int i=1;i<=tot;++i) if (vis[rat[i].x][rat[i].y]) rat[i].dead=1; break; } // 神秘射线 case 2: { for (int i=1;i<=tot;++i) if (!rat[i].dead&&Dis(rat[i],now)<=R*R) rat[i].re+=3; break; } // 定时炸弹 case 3: { for (int i=1;i<=tot;++i) if (rat[i].x==now.x&&rat[i].y==now.y) rat[i].dead=1; break; } // 生物炸弹 case 4: { for (int i=1;i<=tot;++i) if (rat[i].x==now.x&&rat[i].y==now.y) rat[i].sex^=1; break; } }}void CheckDeath(){ int now=0; for (int i=1;i<=tot;++i) if (!rat[i].dead) bag[++now]=rat[i]; tot=now; for (int i=1;i<=tot;++i) rat[i]=bag[i];}void Move(){ for (int i=1;i<=tot;++i) { // 如果未恢复生理活动或者处于繁殖完的休息或者在繁殖中都不能移动 if (rat[i].re||rat[i].move>0||rat[i].multi!=-1) continue; int x=rat[i].x,y=rat[i].y; int d=rat[i].dir,dl=(d-1+4)%4,dr=(d+1)%4,db=(d+2)%4; // 只要前方有管道 if (loc[x][y]&trans[d]) { rat[i].x=x+dx[d],rat[i].y=y+dy[d]; continue; } // 两边都有路 if ((loc[x][y]&trans[dl])&&(loc[x][y]&trans[dr])) { ++rat[i].cnt; if (rat[i].cnt&1) rat[i].dir=dl; else rat[i].dir=dr; continue; } // 左边有管道右边无管道 if ((loc[x][y]&trans[dl])&&((loc[x][y]&trans[dr])==0)) { rat[i].dir=dl; continue; } // 右边有管道左边无管道 if ((loc[x][y]&trans[dr])&&((loc[x][y]&trans[dl])==0)) { rat[i].dir=dr; continue; } // 死路向右转 rat[i].dir=dr; }}void Arrange(){ for (int i=1;i<=tot;++i) { if (!rat[i].re) ++rat[i].age; if (!rat[i].re&&rat[i].multi!=-1) --rat[i].multi; if (!rat[i].re&&rat[i].move!=-1) --rat[i].move; if (rat[i].re) --rat[i].re; }}int main(){ scanf("%d%d%d%d",&L,&R,&n,&m); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) scanf("%d",&loc[i][j]); scanf("%d/n",&tot); for (int i=1;i<=tot;++i) { char c1,c2; scanf("%d %d %c %c/n",&rat[i].x,&rat[i].y,&c1,&c2); switch (c1) { case 'N':rat[i].dir=0;break; case 'E':rat[i].dir=1;break; case 'S':rat[i].dir=2;break; case 'W':rat[i].dir=3;break; } if (c2=='X') rat[i].sex=0; else rat[i].sex=1; rat[i].cnt=rat[i].re=rat[i].dead=0; rat[i].multi=rat[i].move=-1;rat[i].age=5; } scanf("%d%d",&P,&limit); for (int i=1;i<=P;++i) { scanf("%d%d%d%d",&gun[i].type,&gun[i].t,&gun[i].x,&gun[i].y); if (gun[i].type==3) gun[i].t+=3; } sort(gun+1,gun+P+1); scanf("%d",&T);now=1; for (int i=0;i<=T;++i) { // start the second // 老鼠进行繁殖 Multi(); // 放置武器，攻击老鼠 while (now<=P&&gun[now].t<=i) { Attack(gun[now]); ++now; } CheckDeath(); if (tot>limit) { plague=1; break; } // 老鼠进行移动 Move(); // end the second Arrange(); } if (plague) puts("-1"); else PRintf("%d/n",tot);}

上一篇：ASP.NET中制作各种3D图表的方法

下一篇：【面试题】剑指offer 15