BZOJ1033 | ZJOI2008 杀蚂蚁 AntBuster

Leave a Comment

<论一次杀蚂蚁的经历>

<论如何优雅地用工程代码风格写出杀蚂蚁>

引子：

前天(也就是2018-3-18)的时候，刷B站（BZOJ）突然想起要A这题……

于是怂恿WHY一起做……

然鹅种种原因，拖到昨天（2018-3-19）下午才开始做

于是在CYYZ群里开起了校车……

然后

因为巨长的变量名不想手残于是换了VSCode……

然后疯狂盖楼……

 

注意这已经是今天的中午了……，而我交了一遍得了30

下午来了遂调试……发现了几个zz错误

等级没算对啦……sort忘记+1啦……蚂蚁位置忘记更新啦……以及更为严重的，没算点积判断附加攻击到底能不能打到。

晚上开始怀疑人生……此时代码量超过10k

下载了测试数据本地测……开Lemon却不小心点了O2

结果最后半个小时在静态查错，然而并没有什么错，后来的手动测试也证明了这一点

是Lemon开了O2之后，把程序跑错了

我果然花了几乎1h试图卡掉通过开了O2的Lemon……（滑稽）

管他的，进入正题

 

 

 

 

1.构建大框架

我们需要先声明一些变量

//structures
struct ant_struct
{
	int default_blood,cnt_blood;
	int level,birth_code;
	int cnt_x,cnt_y,pre_w;
	int activ_time;
};

struct tower_struct
{
	int tpos_x,tpos_y;
};

//variables
	//map
	int map_size_x,map_size_y;
	int cnt_map[10][10]={0};
	//tower
	int tower_num,tower_damage,tower_range;
	tower_struct towers[100]={0};
	//ant
	int cnt_ant_num=0,tot_ant_num=0;
	bool ant_map[10][10]={0};
	
	ant_struct ant_que[10];
	int ant_que_len=0;
	//cake
	int target;
	//overall variables
	int tot_time,cnt_time=0;
	int wayx[4]={0,1,0,-1},wayy[4]={1,0,-1,0};

注意高亮的部分，我们会经常使用他们。

·

然后是一些函数的Declearation

// declearation
inline void readx(int&);
inline void input_overall();
inline void birth_an_ant();
inline bool cmp_ant_birth(ant_struct,ant_struct);
inline bool cmp_ant_birth_rev(ant_struct,ant_struct);
inline void ant_excrate();
inline void move_ant(int);
inline void ant_take();
inline void get_older_and_get_lost();
inline void process_death();
inline double get_distance_lp(int,int,int,int);
inline double get_distance_pp(int,int,int,int);
inline void attack_judge(int,int);
inline void tower_attack();
inline bool end_game();
inline void ending_output();
inline bool tot_process();
inline void output_map_info();
inline void output_ant_info();

当然了，构建的时候当然是慢慢添加的，而不是一开始就全部声明。

最后，我们需要确定一下功能块

  1. 读入
  2. 关于蚂蚁的部分
  3. 炮塔攻击模块
  4. 判定游戏结束
  5. 一个总过程，只要不停地调用它就可以了
  6. Debug用的输出函数，Debug的时候只要调用即可
  7. 最后当然还有一个主函数

对于每个函数，我们应该这样规范

type function(variable a,variable b)
{
    //variables
    .....
    //function
    ....
    
    return type;
}

前面是函数内局部变量，然后是一个空行，然后是函数的功能部分。

函数与函数之间空行

哦，对了，还有就是多写注释。

现在我们开始实现读入部分

先写一个快速读入

//input
inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

没啥好说的，下面是读入数据。

inline void input_overall()
{
	//variables
	int tower_posx_cache,tower_posy_cache;
	//read input
	readx(map_size_x); readx(map_size_y);
	readx(tower_num); readx(tower_damage); readx(tower_range);
	for (int i1=1;i1<=tower_num;i1++)
	{
		readx(tower_posx_cache); readx(tower_posy_cache);
		cnt_map[tower_posx_cache][tower_posy_cache]=-1;
		//-1 stands for unreachable
		towers[i1].tpos_x=tower_posx_cache;
		towers[i1].tpos_y=tower_posy_cache;
	}
	readx(tot_time);
}

第一是在当前地图cnt_map里用-1标明是塔，第二是在塔的结构体里面存好位置

到了蚂蚁的部分了

我们考虑用一个队列来操作蚂蚁，那就先写两个函数，方便把队列按照题意排好

inline bool cmp_ant_birth(ant_struct ant1,ant_struct ant2)
{
    return ant1.birth_code<ant2.birth_code;
}

inline bool cmp_ant_birth_rev(ant_struct ant1,ant_struct ant2)
{
    return ant1.activ_time>ant2.activ_time;
}

这里面cmp_ant_birth是按照出生时间排序，cmp_ant_birth_rev是反过来。

乍一看birth_code没多大用处，但是实际上这方便了把死蚂蚁踢出队列。

·  ·  ·  ·

然后该到生成一个蚂蚁了

首先

if (ant_que_len==6) return;
for (int i1=1;i1<=ant_que_len;i1++) if ((!ant_que[i1].cnt_x) && (!ant_que[i1].cnt_y)) return;

这两个限制条件，一个是堵洞口，一个是满队列

ant_que[ant_que_len].cnt_x=ant_que[ant_que_len].cnt_y=0;
ant_que[ant_que_len].level=((tot_ant_num-1)/6)+1;
ant_que[ant_que_len].birth_code=tot_ant_num;

cnt_x和cnt_y表示位置，level是等级，birth_code是出生的序号

特别注意等级的计算

blood_cache1=4.0*pow(1.1,ant_que[ant_que_len].level);
blood_cache2=(int)floor(blood_cache1);

ant_que[ant_que_len].default_blood=blood_cache2;
ant_que[ant_que_len].cnt_blood=ant_que[ant_que_len].default_blood;
ant_que[ant_que_len].activ_time=1;
ant_que[ant_que_len].pre_w=4;

算一下血量，记录下上一步的方向（当然是原地不动）和年龄

一气呵成！

//about ants
inline void birth_an_ant()
{
	if (ant_que_len==6) return;
	for (int i1=1;i1<=ant_que_len;i1++) if ((!ant_que[i1].cnt_x) && (!ant_que[i1].cnt_y)) return;
	
	//variables
	double blood_cache1;
	int blood_cache2;
	//functions
	ant_que_len++; tot_ant_num++;
	
	ant_que[ant_que_len].cnt_x=ant_que[ant_que_len].cnt_y=0;
	ant_que[ant_que_len].level=((tot_ant_num-1)/6)+1;
	ant_que[ant_que_len].birth_code=tot_ant_num;
	
	blood_cache1=4.0*pow(1.1,ant_que[ant_que_len].level);
	blood_cache2=(int)floor(blood_cache1);
	
	ant_que[ant_que_len].default_blood=blood_cache2;
	ant_que[ant_que_len].cnt_blood=ant_que[ant_que_len].default_blood;
	ant_que[ant_que_len].activ_time=1;
	ant_que[ant_que_len].pre_w=4;
	
	ant_map[0][0]=true;
}

ant_map是记录蚂蚁位置的地图，true表示这儿有蚂蚁。

到了分泌信号素了

inline void ant_excrate()
{
	for (int i1=1;i1<=ant_que_len;i1++)
	{
		if (target==i1) cnt_map[ant_que[i1].cnt_x][ant_que[i1].cnt_y]+=5;
		else cnt_map[ant_que[i1].cnt_x][ant_que[i1].cnt_y]+=2;
	}
}

很简单，枚举每只蚂蚁，注意特判target

在这里target表示在que中的位置，0意味着不存在target

inline void ant_take()
{
	for (int i1=1;i1<=ant_que_len;i1++)
	{
		if (ant_que[i1].cnt_x==map_size_x && ant_que[i1].cnt_y==map_size_y && !target)
		{
			ant_que[i1].cnt_blood=min(ant_que[i1].default_blood,ant_que[i1].cnt_blood+ant_que[i1].default_blood/2);
			target=i1;
		}
	}
}

这是蚂蚁拿蛋糕的部分，注意有强约束条件 !target

代码比较长，滑着看。 这一部分也很简单。注意血量上限即可，取min

移动蚂蚁，我们用一个合法数组，这样比较方便

bool can_w[5]={1,1,1,1,0};
int ant_x=ant_que[quepos].cnt_x,ant_y=ant_que[quepos].cnt_y;
int most_excrate=0,final_w=4;

can_w就是了。most_excrate 分泌素最多是多少 final_w是最终的方向，默认卡住不动。

用了ant_x和ant_y缩短代码长度。

// condition 1
can_w[ant_que[quepos].pre_w]=false;

条件1

// condition 2
for (int w1=0;w1<=3;w1++) 
	if (ant_x+wayx[w1]<0 || ant_x+wayx[w1]>map_size_x || ant_y+wayy[w1]<0 || ant_y+wayy[w1]>map_size_y)
		can_w[w1]=false;

不能越界

// condition 3
for (int w1=0;w1<=3;w1++)
	if (cnt_map[ant_x+wayx[w1]][ant_y+wayy[w1]]==-1 || ant_map[ant_x+wayx[w1]][ant_y+wayy[w1]]==true)
		can_w[w1]=false;

塔和蚂蚁

//most excrate finding
for (int w1=0;w1<=3;w1++) 
    if (can_w[w1]) 
	   most_excrate=max(most_excrate,cnt_map[ant_x+wayx[w1]][ant_y+wayy[w1]]);

啊哈？找一个最大的分泌素

//turn around
for (int w1=0;w1<=3;w1++) if (can_w[w1] && cnt_map[ant_x+wayx[w1]][ant_y+wayy[w1]]==most_excrate)
{
	final_w=w1;
	break;
}
//can't move
if (final_w==4) { ant_que[quepos].pre_w=4; return; }

转身，附带卡住的情况

//special condition
if (!(ant_que[quepos].activ_time%5))
{
	do
	{
		final_w--;
		if (final_w==-1) final_w=3;
	} while (!can_w[final_w]);
}

神奇的限制

inline void move_ant(int quepos)
{
	//variables
	bool can_w[5]={1,1,1,1,0};
	int ant_x=ant_que[quepos].cnt_x,ant_y=ant_que[quepos].cnt_y;
	int most_excrate=0,final_w=4;
	//functions
		// condition 1
		can_w[ant_que[quepos].pre_w]=false;
		// condition 2
		for (int w1=0;w1<=3;w1++) 
			if (ant_x+wayx[w1]<0 || ant_x+wayx[w1]>map_size_x || ant_y+wayy[w1]<0 || ant_y+wayy[w1]>map_size_y)
				can_w[w1]=false;
		// condition 3
		for (int w1=0;w1<=3;w1++)
			if (cnt_map[ant_x+wayx[w1]][ant_y+wayy[w1]]==-1 || ant_map[ant_x+wayx[w1]][ant_y+wayy[w1]]==true)
				can_w[w1]=false;
		//biggest excrate finding
		for (int w1=0;w1<=3;w1++) if (can_w[w1]) most_excrate=max(most_excrate,cnt_map[ant_x+wayx[w1]][ant_y+wayy[w1]]);
		//turn around
		for (int w1=0;w1<=3;w1++) if (can_w[w1] && cnt_map[ant_x+wayx[w1]][ant_y+wayy[w1]]==most_excrate)
		{
			final_w=w1;
			break;
		}
		//can't move
		if (final_w==4) { ant_que[quepos].pre_w=4; return; }
		
		//special condition
		if (!(ant_que[quepos].activ_time%5))
		{
			do
			{
				final_w--;
				if (final_w==-1) final_w=3;
			} while (!can_w[final_w]);
		}
	
	//move!
	ant_map[ant_x][ant_y]=false;
	ant_map[ant_x+wayx[final_w]][ant_y+wayy[final_w]]=true;
	ant_que[quepos].pre_w=(final_w+2)%4;
	ant_que[quepos].cnt_x+=wayx[final_w];
	ant_que[quepos].cnt_y+=wayy[final_w];
}

最后几行是更新的。
完事了！

蚂蚁变老，起一个比较文艺的名字。

inline void get_older_and_get_lost()
{
	for (int i1=1;i1<=ant_que_len;i1++) ant_que[i1].activ_time++;
	
	for (int i1=0;i1<=map_size_x;i1++)
		for (int i2=0;i2<=map_size_y;i2++)
			if (cnt_map[i1][i2]>=1)
				cnt_map[i1][i2]--;
}

这个没啥好说的……

inline void process_death()
{
	if (!ant_que_len) return;
	//variables
	int pre_ant_que_len=ant_que_len;
	int birth_of_tar=ant_que[target].birth_code;
	//functions
	for (int i1=1;i1<=pre_ant_que_len;i1++)
	{
		if (ant_que[i1].cnt_blood<0)
		{
			if (i1==target) target=0;
			ant_que[i1].birth_code=1e9;
			ant_que_len--;
			ant_map[ant_que[i1].cnt_x][ant_que[i1].cnt_y]=0;
		}
	}
	sort(ant_que+1,ant_que+pre_ant_que_len+1,cmp_ant_birth);
	
	if (target) for (int i1=1;i1<=ant_que_len;i1++)
		if (ant_que[i1].birth_code==birth_of_tar)
			target=i1;
}

判定死蚂蚁踢出队列，这里我们直接把蚂蚁的birth_code赋值无限大然后排序，注意记录原队列长度和现队列长度并且不要搞混

还有就是最后的部分,更新Target

这是我最后一个Bug，我在写的时候反复提醒过自己不要漏掉这个部分

结果还是漏了……并且没想起来。

下面是塔的部分

inline double get_distance_lp(int x1w,int y1w,int x2w,int y2w)
{
	return (double)abs(x1w*y2w-x2w*y1w)/sqrt(pow(x1w,2)+pow(y1w,2));
}

inline double get_distance_pp(int x1w,int y1w,int x2w,int y2w)
{
	return sqrt(pow(x1w-x2w,2)+pow(y1w-y2w,2));
}

inline bool get_distance_sp(int x1w,int y1w,int x2w,int y2w,int x3w,int y3w)
{
	if (x1w*x2w+y1w*y2w<0) return false;
	if (x1w*x3w+y1w*y3w>0) return false;
	return true;
}

第一个是给出两个向量，计算第二个向量的x2,y2端点（一个是0,0,一个x2,y2）距离第一个向量所在直线的距离。用了叉积

第二个是两点间欧氏距离

第三个是用点积判断C点到向量AB的垂线会不会交AB

函数和图的变量不匹配。

函数里的x1y1是向量AB，x2y2是AC，x3y3是平移过的BC

完事了。

inline void tower_attack()
{
	//variables
	int tar_ant=0;
	double mindis=100000000.00,cache_dis;
	
	//functions
	for (int i1=1;i1<=tower_num;i1++)
	{
		//init
		mindis=100000000.00; tar_ant=0; cache_dis=0;
		//attack
		if (target && get_distance_pp(towers[i1].tpos_x,towers[i1].tpos_y,
									  ant_que[target].cnt_x,ant_que[target].cnt_y)<=tower_range)
		{
			ant_que[target].cnt_blood-=tower_damage;
			attack_judge(i1,target);
		}
		
		else
		{
			for (int i2=1;i2<=ant_que_len;i2++)
			{
				cache_dis=get_distance_pp(towers[i1].tpos_x,towers[i1].tpos_y,ant_que[i2].cnt_x,ant_que[i2].cnt_y);
				if (cache_dis<=tower_range && cache_dis<mindis)
				{
					mindis=cache_dis;
					tar_ant=i2;
				}
			}//expelled target ant(sorted by birth code)
			if (tar_ant) ant_que[tar_ant].cnt_blood-=tower_damage;
		}
	}
	
}<span id="mce_marker" data-mce-type="bookmark" data-mce-fragment="1">​</span>

上一半是存在Target，用函数get_distance_pp判一下能打到，就打他，并且处理附加伤害

或者达不到或者没有的情况，那找一个最近的蚂蚁（别忘了队列始终是birth_code排序的？）

用get_distance_pp，更新mindis，记录tar_ant。tar_ant就是你要攻击的那个蚂蚁。

这个是处理附加伤害，枚举蚂蚁并判一下不是原本的蚂蚁，然后构建向量判定就行了。

inline void attack_judge(int tower_code,int ant_code)
{
	//variables
	int vec1_x,vec1_y,vec2_x,vec2_y,vec3_x,vec3_y;
	//functions
	vec1_x=ant_que[ant_code].cnt_x-towers[tower_code].tpos_x;
	vec1_y=ant_que[ant_code].cnt_y-towers[tower_code].tpos_y;
	
	for (int i1=1;i1<=ant_que_len;i1++) if (i1!=ant_code)
	{
		vec2_x=ant_que[i1].cnt_x-towers[tower_code].tpos_x;
		vec2_y=ant_que[i1].cnt_y-towers[tower_code].tpos_y;
		
		vec3_x=ant_que[i1].cnt_x-ant_que[ant_code].cnt_x;
		vec3_y=ant_que[i1].cnt_y-ant_que[ant_code].cnt_y;
		
		if (get_distance_lp(vec1_x,vec1_y,vec2_x,vec2_y)<=0.5000)
			if (get_distance_sp(vec1_x,vec1_y,vec2_x,vec2_y,vec3_x,vec3_y))
				ant_que[i1].cnt_blood-=tower_damage;
	}
}
//ending
inline bool end_game()
{
	if (target!=0 && (!ant_que[target].cnt_x) && (!ant_que[target].cnt_y)) return true;
	return false;
}

inline void ending_output()
{
	printf("%d\n",ant_que_len);
	sort(ant_que+1,ant_que+ant_que_len+1,cmp_ant_birth_rev);
	for (int i1=1;i1<=ant_que_len;i1++)
	{
		printf("%d %d %d %d %d\n",
				ant_que[i1].activ_time-1,ant_que[i1].level,ant_que[i1].cnt_blood,ant_que[i1].cnt_x,ant_que[i1].cnt_y);
	}
}

我干脆一块放上来了。

end_game很简单

ending_output不看也行，这是结束后输出的函数。

//tot_process
inline bool tot_process()
{
	birth_an_ant();
	ant_excrate();
	for (int i1=1;i1<=ant_que_len;i1++) move_ant(i1);
	if (!target) ant_take();
	
	tower_attack();
	process_death();
	
	if (end_game()) return true;
	
	get_older_and_get_lost();
	
	return false;
}

处理一秒的事件，你就xjb调用函数就行了，注意顺序。

调试函数我就不放了……

后面是main()

int main()
{
	input_overall();
	
	for (int sec=1;sec<=tot_time;sec++)
	{
		if (tot_process())
		{
			printf("Game over after %d seconds\n",sec);
			ending_output();
			return 0;
		}
	}
	printf("The game is going on\n");
	ending_output();
	
	return 0;
}

大功告成！

·   ·   ·   ·

·   ·   ·   ·

所有的代码：（可能有一些调试注释什么的懒得删了）

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<vector>
using namespace std;

//structures
struct ant_struct
{
	int default_blood,cnt_blood;
	int level,birth_code;
	int cnt_x,cnt_y,pre_w;
	int activ_time;
};

struct tower_struct
{
	int tpos_x,tpos_y;
};

//variables
	//map
	int map_size_x,map_size_y;
	int cnt_map[10][10]={0};
	//tower
	int tower_num,tower_damage,tower_range;
	tower_struct towers[100]={0};
	//ant
	int cnt_ant_num=0,tot_ant_num=0;
	bool ant_map[10][10]={0};
	
	ant_struct ant_que[10];
	int ant_que_len=0;
	//cake
	int target;
	//overall variables
	int tot_time,cnt_time=0;
	int wayx[4]={0,1,0,-1},wayy[4]={1,0,-1,0};

// declearation
inline void readx(int&);
inline void input_overall();
inline void birth_an_ant();
inline bool cmp_ant_birth(ant_struct,ant_struct);
inline bool cmp_ant_birth_rev(ant_struct,ant_struct);
inline void ant_excrate();
inline void move_ant(int);
inline void ant_take();
inline void get_older_and_get_lost();
inline void process_death();
inline double get_distance_lp(int,int,int,int);
inline double get_distance_pp(int,int,int,int);
inline void attack_judge(int,int);
inline void tower_attack();
inline bool end_game();
inline void ending_output();
inline bool tot_process();
inline void output_map_info();
inline void output_ant_info();

//input
inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline void input_overall()
{
	//variables
	int tower_posx_cache,tower_posy_cache;
	//read input
	readx(map_size_x); readx(map_size_y);
	readx(tower_num); readx(tower_damage); readx(tower_range);
	for (int i1=1;i1<=tower_num;i1++)
	{
		readx(tower_posx_cache); readx(tower_posy_cache);
		cnt_map[tower_posx_cache][tower_posy_cache]=-1;
		//-1 stands for unreachable
		towers[i1].tpos_x=tower_posx_cache;
		towers[i1].tpos_y=tower_posy_cache;
	}
	readx(tot_time);
}

//about ants
inline void birth_an_ant()
{
	if (ant_que_len==6) return;
	for (int i1=1;i1<=ant_que_len;i1++) if ((!ant_que[i1].cnt_x) && (!ant_que[i1].cnt_y)) return;
	
	//variables
	double blood_cache1;
	int blood_cache2;
	//functions
	ant_que_len++; tot_ant_num++;
	
	ant_que[ant_que_len].cnt_x=ant_que[ant_que_len].cnt_y=0;
	ant_que[ant_que_len].level=((tot_ant_num-1)/6)+1;
	ant_que[ant_que_len].birth_code=tot_ant_num;
	
	blood_cache1=4.0*pow(1.1,ant_que[ant_que_len].level);
	blood_cache2=(int)floor(blood_cache1);
	
	ant_que[ant_que_len].default_blood=blood_cache2;
	ant_que[ant_que_len].cnt_blood=ant_que[ant_que_len].default_blood;
	ant_que[ant_que_len].activ_time=1;
	ant_que[ant_que_len].pre_w=4;
	
	ant_map[0][0]=true;
}

inline bool cmp_ant_birth(ant_struct ant1,ant_struct ant2) { return ant1.birth_code<ant2.birth_code; }
inline bool cmp_ant_birth_rev(ant_struct ant1,ant_struct ant2) { return ant1.activ_time>ant2.activ_time; }

inline void ant_excrate()
{
	for (int i1=1;i1<=ant_que_len;i1++)
	{
		if (target==i1) cnt_map[ant_que[i1].cnt_x][ant_que[i1].cnt_y]+=5;
		else cnt_map[ant_que[i1].cnt_x][ant_que[i1].cnt_y]+=2;
	}
}

inline void move_ant(int quepos)
{
	//variables
	bool can_w[5]={1,1,1,1,0};
	int ant_x=ant_que[quepos].cnt_x,ant_y=ant_que[quepos].cnt_y;
	int most_excrate=0,final_w=4;
	//functions
		// condition 1
		can_w[ant_que[quepos].pre_w]=false;
		// condition 2
		for (int w1=0;w1<=3;w1++) 
			if (ant_x+wayx[w1]<0 || ant_x+wayx[w1]>map_size_x || ant_y+wayy[w1]<0 || ant_y+wayy[w1]>map_size_y)
				can_w[w1]=false;
		// condition 3
		for (int w1=0;w1<=3;w1++)
			if (cnt_map[ant_x+wayx[w1]][ant_y+wayy[w1]]==-1 || ant_map[ant_x+wayx[w1]][ant_y+wayy[w1]]==true)
				can_w[w1]=false;
		//biggest excrate finding
		for (int w1=0;w1<=3;w1++) if (can_w[w1]) most_excrate=max(most_excrate,cnt_map[ant_x+wayx[w1]][ant_y+wayy[w1]]);
		//turn around
		for (int w1=0;w1<=3;w1++) if (can_w[w1] && cnt_map[ant_x+wayx[w1]][ant_y+wayy[w1]]==most_excrate)
		{
			final_w=w1;
			break;
		}
		//can't move
		if (final_w==4) { ant_que[quepos].pre_w=4; return; }
		
		//special condition
		if (!(ant_que[quepos].activ_time%5))
		{
			do
			{
				final_w--;
				if (final_w==-1) final_w=3;
			} while (!can_w[final_w]);
		}
	
	//move!
	ant_map[ant_x][ant_y]=false;
	ant_map[ant_x+wayx[final_w]][ant_y+wayy[final_w]]=true;
	ant_que[quepos].pre_w=(final_w+2)%4;
	ant_que[quepos].cnt_x+=wayx[final_w];
	ant_que[quepos].cnt_y+=wayy[final_w];
}

inline void ant_take()
{
	for (int i1=1;i1<=ant_que_len;i1++)
	{
		if (ant_que[i1].cnt_x==map_size_x && ant_que[i1].cnt_y==map_size_y && !target)
		{
			ant_que[i1].cnt_blood=min(ant_que[i1].default_blood,ant_que[i1].cnt_blood+ant_que[i1].default_blood/2);
			target=i1;
		}
	}
}

inline void get_older_and_get_lost()
{
	for (int i1=1;i1<=ant_que_len;i1++) ant_que[i1].activ_time++;
	
	for (int i1=0;i1<=map_size_x;i1++)
		for (int i2=0;i2<=map_size_y;i2++)
			if (cnt_map[i1][i2]>=1)
				cnt_map[i1][i2]--;
}

inline void process_death()
{
	if (!ant_que_len) return;
	//variables
	int pre_ant_que_len=ant_que_len;
	int birth_of_tar=ant_que[target].birth_code;
	//functions
	for (int i1=1;i1<=pre_ant_que_len;i1++)
	{
		if (ant_que[i1].cnt_blood<0)
		{
			if (i1==target) target=0;
			ant_que[i1].birth_code=1e9;
			ant_que_len--;
			ant_map[ant_que[i1].cnt_x][ant_que[i1].cnt_y]=0;
		}
	}
	sort(ant_que+1,ant_que+pre_ant_que_len+1,cmp_ant_birth);
	
	if (target) for (int i1=1;i1<=ant_que_len;i1++)
		if (ant_que[i1].birth_code==birth_of_tar)
			target=i1;
}

//about tower
inline double get_distance_lp(int x1w,int y1w,int x2w,int y2w)
{
	return (double)abs(x1w*y2w-x2w*y1w)/sqrt(pow(x1w,2)+pow(y1w,2));
}

inline double get_distance_pp(int x1w,int y1w,int x2w,int y2w)
{
	return sqrt(pow(x1w-x2w,2)+pow(y1w-y2w,2));
}

inline bool get_distance_sp(int x1w,int y1w,int x2w,int y2w,int x3w,int y3w)
{
	if (x1w*x2w+y1w*y2w<0) return false;
	if (x1w*x3w+y1w*y3w>0) return false;
	return true;
}

inline void attack_judge(int tower_code,int ant_code)
{
	//variables
	int vec1_x,vec1_y,vec2_x,vec2_y,vec3_x,vec3_y;
	//functions
	vec1_x=ant_que[ant_code].cnt_x-towers[tower_code].tpos_x;
	vec1_y=ant_que[ant_code].cnt_y-towers[tower_code].tpos_y;
	
	for (int i1=1;i1<=ant_que_len;i1++) if (i1!=ant_code)
	{
		vec2_x=ant_que[i1].cnt_x-towers[tower_code].tpos_x;
		vec2_y=ant_que[i1].cnt_y-towers[tower_code].tpos_y;
		
		vec3_x=ant_que[i1].cnt_x-ant_que[ant_code].cnt_x;
		vec3_y=ant_que[i1].cnt_y-ant_que[ant_code].cnt_y;
		
		if (get_distance_lp(vec1_x,vec1_y,vec2_x,vec2_y)<=0.5000)
			if (get_distance_sp(vec1_x,vec1_y,vec2_x,vec2_y,vec3_x,vec3_y))
				ant_que[i1].cnt_blood-=tower_damage;
	}
}

inline void tower_attack()
{
	//variables
	int tar_ant=0;
	double mindis=100000000.00,cache_dis;
	//functions
	for (int i1=1;i1<=tower_num;i1++)
	{
		//init
		mindis=100000000.00; tar_ant=0; cache_dis=0;
		//attack
		if (target && get_distance_pp(towers[i1].tpos_x,towers[i1].tpos_y,
									  ant_que[target].cnt_x,ant_que[target].cnt_y)<=tower_range)
		{
			ant_que[target].cnt_blood-=tower_damage;
			attack_judge(i1,target);
		}
		else
		{
			for (int i2=1;i2<=ant_que_len;i2++)
			{
				cache_dis=get_distance_pp(towers[i1].tpos_x,towers[i1].tpos_y,ant_que[i2].cnt_x,ant_que[i2].cnt_y);
				if (cache_dis<=tower_range && cache_dis<mindis)
				{
					mindis=cache_dis;
					tar_ant=i2;
				}
			}//expelled target ant(sorted by birth code)
			if (tar_ant) ant_que[tar_ant].cnt_blood-=tower_damage;
		}
	}
	
	// for (int i1=1;i1<=ant_que_len;i1++) printf("%d\n",ant_que[i1].cnt_blood);
}

//ending
inline bool end_game()
{
	if (target!=0 && (!ant_que[target].cnt_x) && (!ant_que[target].cnt_y)) return true;
	return false;
}

inline void ending_output()
{
	printf("%d\n",ant_que_len);
	sort(ant_que+1,ant_que+ant_que_len+1,cmp_ant_birth_rev);
	for (int i1=1;i1<=ant_que_len;i1++)
	{
		printf("%d %d %d %d %d\n",
				ant_que[i1].activ_time-1,ant_que[i1].level,ant_que[i1].cnt_blood,ant_que[i1].cnt_x,ant_que[i1].cnt_y);
	}
}

//tot_process
inline bool tot_process()
{
	birth_an_ant();
	ant_excrate();
	for (int i1=1;i1<=ant_que_len;i1++) move_ant(i1);
	if (!target) ant_take();
	
	tower_attack();
	process_death();
	
	if (end_game()) return true;
	
	get_older_and_get_lost();
	
//	output_map_info();
//	output_ant_info();
//	printf("\n");
	return false;
}

//Debug
inline void output_map_info()
{
	printf("-----Output Current Map Info-----\n");
	for (int i1=0;i1<=map_size_x;i1++)
	{
		for (int i2=0;i2<=map_size_y;i2++) printf("%d ",cnt_map[i1][i2]);
		printf("\n");
	}
	printf("-----Output Ant Map Info-----\n");
	for (int i1=0;i1<=map_size_x;i1++)
	{
		for (int i2=0;i2<=map_size_y;i2++) printf("%d ",ant_map[i1][i2]);
		printf("\n");
	}
}

inline void output_ant_info()
{
	printf("----Current Ant Num: %d -----\n",ant_que_len);
	for (int i1=1;i1<=ant_que_len;i1++)
	{
		ant_struct ant1=ant_que[i1];
		printf("Ant %d : (%d,%d) HP=%d Def_HP=%d lev=%d actv=%d\n",ant1.birth_code,ant1.cnt_x,ant1.cnt_y,
				ant1.cnt_blood,ant1.default_blood,ant1.level,ant1.activ_time);
	}
	printf("-----Target= %d-----\n",target);
}

int main()
{
//	freopen("antbuster.debug","w",stdout);
	
	input_overall();
	
	for (int sec=1;sec<=tot_time;sec++)
	{
		if (tot_process())
		{
			printf("Game over after %d seconds\n",sec);
			ending_output();
			return 0;
		}
	}
	printf("The game is going on\n");
	ending_output();
	
	return 0;
}

祝AC愉快！

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.