题解：P7196 [CTSC2002] 灭鼠行动

· · 题解

这一题吧，怎么说呢，读懂题面就做完了一半了。

鉴于本题题意有不少缺失外加数据非常水，仅保证代码可通过本题数据。

还是先明确几个已经在讨论区和题解都被大量提及的注意事项吧：

另外还有几个推论：

接下来就是具体过程了（方法可能较为繁琐，望包涵）。

先看武器的实现。

强力射线：分别向四个方向搜索，标记会被波及的地图位置，碰到墙立刻停下，遍历所有的老鼠，如果在被波及的位置就标记为死亡。

神秘射线：枚举所有老鼠，用勾股定理绕开浮点精度问题，如果会被影响就将其昏迷时间加 3。

定时炸弹：实际上相当于一个 3 刻后放置的瞬爆炸弹，所以直接输入的时候 t 变为 t+3，然后直接将在放置位置的老鼠记为死亡。

生物炸弹：如果在放置位置的老鼠更改性别即可。

再看繁殖和出生。

先扫一遍所有老鼠判断是否满足题述繁殖条件的同时在上次繁殖后动过，每有一对满足繁殖条件的老鼠，直接令其原地休息 3 刻。

再扫一遍所有老鼠，如果有剩余休息时间为 1 刻的老鼠，则在原地生成一只小老鼠。

移动直接参照题意即可。

死路随意左转右转，刚刚出生的小老鼠也要加入移动判定。

最后修正计数器，如果昏迷计数器大于 0 则减一。

否则如果休息计数器大于 0 也减一，如果此次休息计数器正好从 1 变为 0，则标记为繁殖后未动过。最后将年龄计数器加 1。

放代码：

#include<bits/stdc++.h>
using namespace std;
int L,R,m,n,K,P,Limit;
int mousecnt;
bool debug;
int a[105][105];
int d[4]={1,2,4,8};
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool des[55][55];
bool mp[55][55][4];
int weaponp;
int Time;
int T;
struct Mouse{
    int age,deadtime,resttime,x,y,alive,turncnt;
    char forward,sex;
    int sexmove;
}mouse[100005];
struct Weapon{
    int op,t,x,y;
}weapon[100005];
char fwd(int x){
    if(x==0)return 'N';
    else if(x==1)return 'E';
    else if(x==2)return 'S';
    else return 'W';
}
int chg(char x){
    if(x=='N')return 0;
    else if(x=='E')return 1;
    else if(x=='S')return 2;
    return 3;
}
int left(int x){
    if(x!=0)return x-1;
    return 3;
}
int right(int x){
    if(x!=3)return x+1;
    return 0;
}
bool cmp(Weapon a,Weapon b){
    return a.t<b.t;
}
void buildmap(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=3;k>=0;k--){
                if(a[i][j]>=d[k]){
                    a[i][j]-=d[k];
                    mp[i][j][k]=1;
//                  cout<<i<<" "<<j<<" "<<k<<endl;
                }
            }
        }
    }
}
void input(){
    cin>>L>>R>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    buildmap();
    cin>>K;
    for(int i=1;i<=K;i++){
        cin>>mouse[i].x>>mouse[i].y>>mouse[i].forward>>mouse[i].sex;
        mouse[i].age=6;
        mouse[i].deadtime=mouse[i].resttime=0;
        mouse[i].alive=1;
        mouse[i].turncnt=0;
        mouse[i].sexmove=0;
    }
    mousecnt=K;
    weaponp=1;
    cin>>P>>Limit;
    for(int i=1;i<=P;i++){
        cin>>weapon[i].op>>weapon[i].t>>weapon[i].x>>weapon[i].y;
        if(weapon[i].op==3)weapon[i].t+=3;
    }
    sort(weapon+1,weapon+P+1,cmp);
    cin>>Time;
}
void doweapon(){
        int debugcnt=0;
    while(weaponp<=P&&weapon[weaponp].t<=T){
        int x=weapon[weaponp].x,y=weapon[weaponp].y;
        if(weapon[weaponp].op==1){
            memset(des,0,sizeof(des));
            des[x][y]=1;
            bool f[10]={1,1,1,1,1};
            for(int i=1;i<=L;i++){
                if(x-i>=1&&mp[x-i+1][y][0]&&f[0]){
                    des[x-i][y]=1;
                }
                else f[0]=0;
                if(y+i<=m&&mp[x][y+i-1][1]&&f[1]){
                    des[x][y+i]=1;
                }
                else f[1]=0;
                if(x+i<=n&&mp[x+i-1][y][2]&&f[2]){
                    des[x+i][y]=1;
                }
                else f[2]=0;
                if(y-i>=1&&mp[x][y-i+1][3]&&f[3]){
                    des[x][y-i]=1;
                }
                else f[3]=0;
            }
            for(int i=1;i<=K;i++){
                if(mouse[i].alive==0)continue;
                if(des[mouse[i].x][mouse[i].y]){
                mouse[i].alive=0,debugcnt++;
//                  if(T==30)cout<<mouse[i].x<<"|"<<mouse[i].y<<"\n";
                }
            }
        }
        else if(weapon[weaponp].op==2){
            for(int i=1;i<=K;i++){
                if(mouse[i].alive==0)continue;
                if((mouse[i].x-x)*(mouse[i].x-x)+(mouse[i].y-y)*(mouse[i].y-y)<=R*R){
                    mouse[i].deadtime+=3;
                }
            }
        }
        else if(weapon[weaponp].op==3){
            for(int i=1;i<=K;i++){
                if(mouse[i].alive==0)continue;
                if(mouse[i].x==x&&mouse[i].y==y)mouse[i].alive=0,debugcnt++;
            }
        }
        else if(weapon[weaponp].op==4){
            for(int i=1;i<=K;i++){
                if(mouse[i].alive==0)continue;
                if(mouse[i].x==x&&mouse[i].y==y){
                    if(mouse[i].sex=='X')mouse[i].sex='Y';
                    else mouse[i].sex='X';
                }
            }
        }
        weaponp++;
    }
//      if(debug)cout<<debugcnt<<"|"<<endl;
}
int c[55][55][2];
bool sexed[55][55];
void checksex(){
    memset(c,0,sizeof(c));
    for(int i=1;i<=K;i++){
        if(!mouse[i].alive)continue;
        c[mouse[i].x][mouse[i].y][mouse[i].sex=='X']++;
        if(mouse[i].age<5||mouse[i].deadtime!=0||mouse[i].resttime!=0||mouse[i].sexmove==1)c[mouse[i].x][mouse[i].y][mouse[i].sex=='X']++;
    }
    for(int i=1;i<=K;i++){
        if(!mouse[i].alive)continue;
        if(mouse[i].deadtime!=0||mouse[i].resttime!=0||mouse[i].age<5)continue;
        if(c[mouse[i].x][mouse[i].y][0]==1&&c[mouse[i].x][mouse[i].y][1]==1){
            mouse[i].resttime=3;
        }
    }
}
void checkborn(){
    memset(sexed,0,sizeof(sexed));
    for(int i=1;i<=K;i++){
        if(!mouse[i].alive)continue;
        if(mouse[i].deadtime!=0||mouse[i].age<5)continue;
        if(mouse[i].resttime==1&&!sexed[mouse[i].x][mouse[i].y]){
            sexed[mouse[i].x][mouse[i].y]=1;
            for(int k=0;k<=3;k++){
                if(mp[mouse[i].x][mouse[i].y][k]){
//                  if(debug==1)cout<<mouse[i].x<<" "<<mouse[i].y<<" "<<k<<"sfds\n";
                    mouse[++K].age=0;
                    mouse[K].alive=1;
                    mouse[K].deadtime=mouse[K].resttime=0;
                    mouse[K].x=mouse[i].x;
                    mouse[K].y=mouse[i].y;
                    mouse[K].forward=fwd(k);
                    mouse[K].sex=(k%2==0?'X':'Y');
                    mouse[K].turncnt=0;
                    mouse[K].sexmove=0;
//                  cout<<mouse[K].x<<"|"<<mouse[K].y<<" "<<mouse[K].forward<<endl;
                }
            }
        }
    }
}
void walk(){
    for(int i=1;i<=K;i++){
        if(!mouse[i].alive)continue;
        if(mouse[i].deadtime!=0||mouse[i].resttime!=0)continue;
        mouse[i].sexmove=0;
        if(mp[mouse[i].x][mouse[i].y][chg(mouse[i].forward)]){
//          cout<<i<<"A"<<endl;
            mouse[i].x+=dx[chg(mouse[i].forward)];
            mouse[i].y+=dy[chg(mouse[i].forward)];
        }
        else{
//          if(mouse[i].x==1&&mouse[i].y==3)cout<<left(chg(mouse[i].forward))<<" "<<mp[mouse[i].x][mouse[i].y][3]<<"s\n";
            if(mp[mouse[i].x][mouse[i].y][left(chg(mouse[i].forward))]){
                if(mp[mouse[i].x][mouse[i].y][right(chg(mouse[i].forward))]){
                    mouse[i].turncnt++;
                    if(mouse[i].turncnt%2==1){
                        mouse[i].forward=fwd(left(chg(mouse[i].forward)));
                    }
                    else{
                        mouse[i].forward=fwd(right(chg(mouse[i].forward)));
                    }
                }
                else{
                    mouse[i].forward=fwd(left(chg(mouse[i].forward)));
                }
            }
            else if(mp[mouse[i].x][mouse[i].y][right(chg(mouse[i].forward))]){
//              if(mouse[i].x==1&&mouse[i].y==3)cout<<"ADSAD\n";
                mouse[i].forward=fwd(right(chg(mouse[i].forward)));
            }
            else{
//              if(mouse[i].x==1&&mouse[i].y==3)cout<<"ADSAD\n";
                mouse[i].forward=fwd(right(chg(mouse[i].forward)));
            }
        }
    }
}
void downcnt(){
    for(int i=1;i<=K;i++){
        if(!mouse[i].alive)continue;
        if(mouse[i].deadtime>0)mouse[i].deadtime--;
        else if(mouse[i].resttime>0){
            mouse[i].resttime--;
            if(mouse[i].resttime==0)mouse[i].sexmove=1;
        }
        else mouse[i].age++;
    }
}

//int debug(char x){
//  if(x=='N')return 1;
//  else if(x=='E')return 2;
//  else if(x=='S')return 4;
//  else return 8;
//}
int main(){
//  freopen("mouse.in","r",stdin);
//  freopen("test1.out","w",stdout);
    input();
    for(;T<=Time;T++){
        if(T==30)debug=1;
        else debug=0;
        doweapon();
//      cout<<"ENDWEAPON\n";
        checkborn();
        checksex();
        walk();
        downcnt();
//      if(debug)cout<<"P\n";
        int C=0;
        for(int i=1;i<=K;i++){
            if(!mouse[i].alive)continue;
//          cout<<mouse[i].x<<" "<<mouse[i].y<<" "<<debug(mouse[i].forward)<<"\n";
            C++;
        }
        if(C>Limit){
            cout<<"-1";
            return 0;
        }
//      cout<<T<<endl;
//      cout<<C<<endl;
    }
    int ans=0;
    for(int i=1;i<=K;i++){
        if(!mouse[i].alive)continue;
//      cout<<mouse[i].x<<" "<<mouse[i].y<<" "<<mouse<<"\n";
        ans++;
    }
    cout<<ans;
    return 0;
}
//武器>繁殖>出生>行动=成长。