P2586 杀蚂蚁30pts求助,有注释
  • 板块学术版
  • 楼主1Stone
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/9/16 15:10
  • 上次更新2023/10/27 11:27:16
查看原帖
P2586 杀蚂蚁30pts求助,有注释
648953
1Stone楼主2022/9/16 15:10

调了好久了,应该是攻击那里的式子出了问题,要么就是蚂蚁移动有些奇奇怪怪的问题

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int cake_x,cake_y,nw_alive,tg,R,D,Ant_num,N,M,S,T,dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
//nw_alive为现存蚂蚁的个数,Ant_num为蚂蚁的最大编号,tg记录target是在Ant中的编号
//N为行数,M为列数,cake_x为蛋糕所在的横坐标,cake_y为蛋糕所在的纵坐标
//xinxi[i][j]表示第i行第j列的信息素个数,vs[i][j]表示第i行第j列是否有蚂蚁
//bz表示蛋糕是否被搬走 
int xinxi[10][10];
bool bz,vs[10][10]; 
struct ant{
    int id,age,ol,nl,x,y,k;//id表示蚂蚁的出生编号,age为蚂蚁的存活时间(年龄),ol为初始生命 
    bool targ;//targ表示是否是target,nl为现在的生命,(x,y)为其坐标 ,k是级别 
}Ant[100];
struct pt{
    int x,y;//(x,y)为其坐标
}Pt[25];
bool cmp(ant a,ant b)
{
    return a.id<b.id;//按出生顺序从小到大排序 
}
void Init()
{
    memset(xinxi,0,sizeof(xinxi));//初始化,地图上无信息素 
    memset(vs,0,sizeof(vs));
    Ant_num=0;//没有蚂蚁出生 
    cake_x=N;//场上没有蚂蚁 
    cake_y=M;//蛋糕在(N,M) 
    bz=0;
    nw_alive=0;
    tg=0;//没被搬走,没有target 
}
bool Done()//游戏是否结束 
{
    if(bz&&Ant[tg].nl>=0&&Ant[tg].x==0&&Ant[tg].y==0)return 1;
    return 0;
}
void Brith()//新蚂蚁出生 
{
    if(nw_alive>=6||vs[0][0])return;//不能出生 
    Ant_num++;//出生一只新蚂蚁,最大编号与场上个数增加 
    nw_alive++;
    Ant[nw_alive].x=0;
    Ant[nw_alive].y=0;//初始在点(0,0) 
    Ant[nw_alive].id=Ant_num;//编号为最大编号 
    Ant[nw_alive].k=ceil(Ant_num*1.0/6);//级别 
    Ant[nw_alive].ol=floor(4*pow(1.1,Ant[nw_alive].k));//初始血量 
    Ant[nw_alive].nl=Ant[nw_alive].ol;//现在血量 
    Ant[nw_alive].age=0;//活动时间是0
    Ant[nw_alive].targ=0;
    vs[0][0]=1;
    sort(Ant+1,Ant+nw_alive+1,cmp); 
}
void You_are_target(int s)
{
    tg=s;
    bz=1;
    Ant[s].targ=1;//成为target
    Ant[s].nl+=floor(Ant[s].ol*1.0/2);
    Ant[s].nl=min(Ant[s].nl,Ant[s].ol);
}
bool Can_be_target(int s)//是否可以成为target 
{
    if(bz||Ant[s].x!=M||Ant[s].y!=N)return 0;
    return 1;
}
void Leave_xinxi()//留下信息素 
{
    for(int i=1;i<=nw_alive;i++)
    {
        if(Ant[i].targ==1)xinxi[Ant[i].x][Ant[i].y]+=5;
        else xinxi[Ant[i].x][Ant[i].y]+=2;
    }
}
int shun_net(int x)//顺时针 
{
    if(x==3)return 0;
    else return x+1;
}
int ni_net(int x)//逆时针 
{
    if(x==0)return 3;
    else return x-1;
}
void Move()//移动 
{
    sort(Ant+1,Ant+nw_alive+1,cmp);//排序 
    for(int i=1;i<=nw_alive;i++)//逐个移动 
    {
        int maxs=-1,f;//f为选定的方向 
        for(int j=0;j<4;j++)
        {
            int zx=Ant[i].x+dx[j],zy=Ant[i].y+dy[j];
            if(zx<0||zy<0||zx>N||zy>M||vs[zx][zy])continue;
            if(maxs<xinxi[zx][zy])
            {
                maxs=xinxi[zx][zy];
                f=j;
            }
        }
        if(maxs==-1) {//不能移动 
                if(Can_be_target(i))You_are_target(i);
                continue;
        }
        bool ok=1;
        for(int j=0;j<4;j++)
        {
            int zx=dx[j]+Ant[i].x,zy=Ant[i].y+dy[j];
            if(zx<0||zy<0||zx>N||zy>M||vs[zx][zy])continue;
            if(maxs!=xinxi[zx][zy])ok=0;
        }
        if(ok)//四周可达点信息素都相同 
        {
            for(int j=3;;j=shun_net(j))//从东开始顺时针选 
            {
                int zx=Ant[i].x+dx[j],zy=Ant[i].y+dy[j];
                if(zx<0||zy<0||zx>N||zy>M||vs[zx][zy])continue;
                f=j;//选定方向 
                break;
            }
        }
        if((Ant[i].age+1)%5==0)//时间是5的倍数,在原先基础上继续选方向 
        {
            for(int j=ni_net(f);;j=ni_net(j))
            {
                int zx=Ant[i].x+dx[j],zy=Ant[i].y+dy[j];
                if(zx<0||zy<0||zx>N||zy>M||vs[zx][zy])continue;         
                f=j;//方向选定 
                break;
            }
        }
        int zx=Ant[i].x+dx[f],zy=Ant[i].y+dy[f];
        vs[Ant[i].x][Ant[i].y]=0;//离开起点 
        vs[zx][zy]=1;//标记终点 
        Ant[i].x=zx;
        Ant[i].y=zy;//改变坐标 
        if(Can_be_target(i))You_are_target(i);//判target 
    }
}
int dist(int nw,int to)//计算Ant[to]到Pt[nw]的距离的平方 
{
    return (Ant[to].x-Pt[nw].x)*(Ant[to].x-Pt[nw].x)+(Ant[to].y-Pt[nw].y)*(Ant[to].y-Pt[nw].y);
} 
void attack(int s)
{
    Ant[s].nl-=D;
}
void get_function(int nw,int mb,int &A,int &B,int &C)//求方程式 
{
    int x1,x2,y1,y2;
    x1=Pt[nw].x;
    y1=Pt[nw].y;
    x2=Ant[mb].x;
    y2=Ant[mb].y;
    A=y1-y2;
    B=x2-x1;
    C=-x2*y1+x1*y2;
}
bool OK(int A,int B,int C,int to)//返回是否可以打击到 
{
    int x0=Ant[to].x,y0=Ant[to].y;
    return 4*(A*x0+B*y0+C)<=(A*A+B*B);//|Ax0+By0+C|/sqrt(A^2+B^2)求点到直线的距离 
}
void Attack()
{
    sort(Ant+1,Ant+nw_alive+1,cmp);//按顺序 
    for(int i=1;i<=S;i++)
    {
        int mb=-1;
        if(dist(i,tg)<=R*R)//能打到target 
        {
            mb=tg;
        }
        else{
            ll mins=1e10;
            for(int j=1;j<=nw_alive;j++)
            {
                int DT=dist(i,j);
                if(DT<=R*R)//能打到 
                {
                    if(mins>DT)//可以更新最小距离 
                    {
                        mins=DT;
                        mb=j;
                    }
                }
            }
        }
        if(mb==-1)continue;//找不到可攻击的 
        int A,B,C;
        get_function(i,mb,A,B,C);//求出炮塔所在点以及目标打击点的直线方程(Ax+By+C=0) 
        for(int j=1;j<=nw_alive;j++)
        {
            //可以被溅射伤害到且激光没有穿透打击 
            if(OK(A,B,C,j)&&Ant[j].x>=min(Ant[mb].x,Pt[i].x)&&Ant[j].x<=max(Ant[mb].x,Pt[i].x)&&Ant[j].y>=min(Ant[mb].y,Pt[i].y)&&Ant[j].y<=max(Ant[mb].y,Pt[i].y))
            {
                attack(j);//攻击 
            }
        }
    }
}
void Died()//清场 
{
    int cnt=0;
    ant A[100];
    for(int i=1;i<=nw_alive;i++)
    {
        if(Ant[i].nl>=0)A[++cnt]=Ant[i];//存活 
        else
        {
            vs[Ant[i].x][Ant[i].y]=0;//清理 
            if(Ant[i].targ==1)//target嗝儿了 
            {
                bz=0;
                tg=0;
            }
        }
    }
    nw_alive=cnt;
    for(int i=1;i<=cnt;i++)Ant[i]=A[i];
}
void New_begin()//信息素减少,年龄增加 
{
    for(int i=0;i<=N;i++)
        for(int j=0;j<=M;j++)
        {
            if(xinxi[i][j]>0)xinxi[i][j]--;
        }
    for(int i=1;i<=nw_alive;i++)
    {
        Ant[i].age++;
    }
}
void Print(bool p,int t)//输出 
{
    if(p)cout<<"Game over after "<<t<<" seconds"<<endl;
    else cout<<"The game is going on"<<endl;
    cout<<nw_alive<<endl;
    sort(Ant+1,Ant+nw_alive+1,cmp);
    for(int i=1;i<=nw_alive;i++)
    {
        cout<<Ant[i].age<<" "<<Ant[i].k<<" "<<Ant[i].nl<<" "<<Ant[i].x<<" "<<Ant[i].y<<endl;
    }
}
void check(int x,int t)//检查用的 
{
    cout<<"Time "<<t<<"  Step "<<x<<endl;
    cout<<"alive:"<<nw_alive<<" Number:"<<Ant_num<<endl;
    cout<<"Graph_information"<<endl;
    for(int i=0;i<=N;i++)
    {
        for(int j=0;j<=M;j++)
        {
            if(vs[i][j])
            {
                bool q=0;
                for(int z=1;z<=S;z++)
                {
                    if(Pt[z].x==i&&Pt[z].y==j)
                    {
                        cout<<"# ";
                        q=1;
                        break;
                    } 
                }   
                if(q)continue;
                cout<<"A ";
            }
            else cout<<xinxi[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"Ants_information"<<endl;
    sort(Ant+1,Ant+nw_alive+1,cmp);
    for(int i=1;i<=nw_alive;i++)
    {
        cout<<"id:"<<Ant[i].id<<" age:"<<Ant[i].age<<" life:"<<Ant[i].nl<<" where("<<Ant[i].x<<","<<Ant[i].y<<")"<<endl;    
    }
    cout<<endl;
}
int main()
{
    cin>>N>>M>>S>>D>>R;
    Init();
    memset(vs,0,sizeof(vs));
    for(int i=1;i<=S;i++){
        cin>>Pt[i].x>>Pt[i].y;
        vs[Pt[i].x][Pt[i].y]=1;
    }
    cin>>T;
    for(int i=1;i<=T;i++)
    {
        Brith();
    //  check(1,i);
        Leave_xinxi();
    //  check(2,i);
        Move();
    //  check(3,i);
        Attack();
    //  check(4,i);
        Died();
    //  check(5,i);
        if(Done())
        {
            Print(1,i);
            return 0;
        }
        New_begin();            
    //  check(6,i);
    }
     Print(0,T);

    return 0;
}
2022/9/16 15:10
加载中...