[BZOJ1033][ZJOI2008]殺螞蟻antbuster（大模擬）

2019-11-08 01:57:52

字體：大中小

供稿：網(wǎng)友

題目描述

傳送門

題解

bz的題面真心不爽，建議去codevs 比較良心的一道大模擬，題面寫的比較清楚，也沒有什么坑

幾個需要注意的地方 1、對于每一只螞蟻來說，年齡=秒數(shù)-1 2、選擇方向的過程是：首先根據(jù)規(guī)則1-3選出一個方向，這個時候判斷如果秒數(shù)不是5的倍數(shù)的話就直接走過去；如果是5的倍數(shù)就按照下一個規(guī)則繼續(xù)選一個方向然后走過去。注意可達(dá)點的定義以及各種前提（先可達(dá)、再信息素最大） 3、殺死一只螞蟻之后，需要更新：地圖，當(dāng)前螞蟻數(shù)量，蛋糕 4、炮攻擊的時候用計算幾何的方法算點線距

剩下的嚴(yán)格根據(jù)題目描述和順序就行了具體看代碼

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 200005double eps=1e-9;int dcmp(double x){ if (x<=eps&&x>=-eps) return 0; return (x>0)?1:-1;}struct Vector{ double x,y; Vector(double X=0,double Y=0) { x=X,y=Y; }};typedef Vector Point;Vector Operator + (Vector a,Vector b) {return Vector(a.x+b.x,a.y+b.y);}Vector operator - (Vector a,Vector b) {return Vector(a.x-b.x,a.y-b.y);}bool operator == (Vector a,Vector b) {return a.x==b.x&&a.y==b.y;}double Dot(Vector a,Vector b){ return a.x*b.x+a.y*b.y;}double Cross(Vector a,Vector b){ return a.x*b.y-a.y*b.x;}double Len(Vector a){ return sqrt(a.x*a.x+a.y*a.y);}double DisTS(Point P,Point A,Point B){ if (A==B) return Len(P-A); Vector v=B-A,w=P-A,u=P-B; if (dcmp(Dot(v,w))<0) return Len(w); else if (dcmp(Dot(v,u))>0) return Len(u); else return fabs(Cross(v,w)/Len(v));}//n,m是地圖范圍，guncnt為炮的個數(shù)，d為每一次攻擊的血量，r為攻擊半徑，t為模擬時間，T為當(dāng)前時間 int n,m,guncnt,d,r,t,T;//螞蟻 struct ANT{ //當(dāng)前位置，上一次的位置 int x,y,lastx,lasty; //年齡（秒數(shù)） int age; //等級 int level; //起始血量，實際血量 int startblood,blood; //是否扛著蛋糕 bool carry;}ant[10];//炮 struct GUN{ //位置 int x,y;}gun[25];//antcnt當(dāng)前螞蟻的總數(shù)，tot所有螞蟻的總數(shù)，cake為扛著蛋糕的螞蟻編號 int antcnt,tot,cake;//mp是地圖，為0表示什么都沒有，為-1表示有炮，為正數(shù)表示有幾只螞蟻 int mp[10][10]; //infor為信息素的值int infor[10][10];//為1.1的n次方，用于算起始血量 double mi[N];//向上、左、下、右走 int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};//判斷游戲是否提前結(jié)束 bool flag;void AntBirth(){ if (antcnt<6&&!mp[0][0]) { ++antcnt;++tot; ant[antcnt].x=ant[antcnt].y=ant[antcnt].lastx=ant[antcnt].lasty=0; ant[antcnt].age=1; ant[antcnt].level=(tot-1)/6+1; ant[antcnt].startblood=ant[antcnt].blood=floor(4*mi[ant[antcnt].level]); ant[antcnt].carry=0; ++mp[0][0]; }}void Information(){ for (int i=1;i<=antcnt;++i) { if (ant[i].carry) infor[ant[i].x][ant[i].y]+=5; else infor[ant[i].x][ant[i].y]+=2; }}void Move(){ // 0 上 2 下 1 左 3 右 for (int i=1;i<=antcnt;++i) { //按照1-3的規(guī)則先選定一個方向 // x,y為這只螞蟻當(dāng)前的點，lastx,lasty為上一次來的點 int x=ant[i].x,y=ant[i].y; int lastx=ant[i].lastx,lasty=ant[i].lasty; // can[i]表示4個方向，向這個方向走是不是可達(dá)點 bool can[4];memset(can,0,sizeof(can)); //nxtx,nxty為下一步到達(dá)的點 //Max為可達(dá)點中信息素的最大值 //cancnt為可達(dá)點個數(shù) int Max=0,cancnt=0; for (int j=0;j<4;++j) { int nxtx=x+dx[j],nxty=y+dy[j]; if (nxtx>=0&&nxtx<=n&&nxty>=0&&nxty<=m&&mp[nxtx][nxty]==0&&(nxtx!=lastx||nxty!=lasty)) { can[j]=1;++cancnt; Max=max(Max,infor[nxtx][nxty]); } } if (!cancnt) { ant[i].lastx=x;ant[i].lasty=y; continue; } int dir=0; for (int j=3;j>=0;--j) { int nxtx=x+dx[j],nxty=y+dy[j]; if (can[j]&&infor[nxtx][nxty]==Max) { dir=j; if (ant[i].age%5==0) break; --mp[x][y];++mp[nxtx][nxty]; ant[i].lastx=x,ant[i].lasty=y; ant[i].x=nxtx,ant[i].y=nxty; break; } } //如果滿足年齡是5的倍數(shù)，順時針旋轉(zhuǎn)，找到一個可達(dá)點 if (ant[i].age%5==0) { for (int j=0;j<4;++j) { ++dir;if (dir==4) dir=0; if (can[dir]) { int nxtx=x+dx[dir],nxty=y+dy[dir]; --mp[x][y];++mp[nxtx][nxty]; ant[i].lastx=x,ant[i].lasty=y; ant[i].x=nxtx,ant[i].y=nxty; break; } } } }}void CarryCake(){ if (cake) return; for (int i=1;i<=antcnt;++i) if (ant[i].x==n&&ant[i].y==m) { ant[i].carry=1;cake=i; //增加血量 ant[i].blood+=ant[i].startblood/2; ant[i].blood=min(ant[i].blood,ant[i].startblood); break; }}int qr(int x){ return x*x;}int length(ANT a,GUN b){ return qr(a.x-b.x)+qr(a.y-b.y);}bool canhit(ANT a,GUN b,ANT c){ Point A=Point(b.x,b.y); Point B=Point(c.x,c.y); Point P=Point(a.x,a.y); double dis=DisTS(P,A,B); if (dcmp(dis-0.5)<=0) return 1; else return 0;}void Attack(){ //length(ant,gun)表示這個螞蟻和這個炮距離的平方 for (int i=1;i<=guncnt;++i) { int goal=0; if (cake&&length(ant[cake],gun[i])<=r*r) goal=cake; else { int Min=100000; for (int j=1;j<=antcnt;++j) { int now=length(ant[j],gun[i]); if (now<=r*r&&now<Min) { Min=now; goal=j; } } } if (!goal) continue; //canhit(i,j,k)表示i這只螞蟻是否在j這個炮和k這個螞蟻的連線上 for (int j=1;j<=antcnt;++j) if (canhit(ant[j],gun[i],ant[goal])) ant[j].blood-=d; }}void CheckDeath(){ int i=1; while (i<=antcnt) { if (ant[i].blood<0) { --mp[ant[i].x][ant[i].y]; for (int j=i;j<antcnt;++j) ant[j]=ant[j+1]; --antcnt; } else ++i; } cake=0; for (int i=1;i<=antcnt;++i) if (ant[i].carry) {cake=i;break;}}bool CheckGame(){ if (!cake) return 0; for (int i=1;i<=antcnt;++i) if (!ant[i].x&&!ant[i].y&&ant[i].carry) return 1; return 0; }int main(){ scanf("%d%d",&n,&m); scanf("%d%d%d",&guncnt,&d,&r); for (int i=1;i<=guncnt;++i) { scanf("%d%d",&gun[i].x,&gun[i].y); mp[gun[i].x][gun[i].y]=-1; } scanf("%d",&t); mi[0]=1.0;for (int i=1;i<=t;++i) mi[i]=mi[i-1]*1.1; for (T=1;T<=t;++T) { //start the second // 出生一只螞蟻 AntBirth(); // 螞蟻留下信息素 Information(); // 將螞蟻移動 Move(); // 螞蟻要扛蛋糕 CarryCake(); // 炮開始攻擊 Attack(); // 檢查螞蟻的死亡情況以及蛋糕是否歸位 CheckDeath(); // 判斷游戲是否結(jié)束 flag=CheckGame(); if (flag) break; for (int i=0;i<=n;++i) for (int j=0;j<=m;++j) if (infor[i][j]) --infor[i][j]; for (int i=1;i<=antcnt;++i) ++ant[i].age; //end the second } if (flag)