模拟战役

题意:回合制游戏......齐齐先手,每次攻击完司机,然后司机打齐齐攻击司机的那一个物品,但是每次会有连锁反应.......真就是我打别人,然后极限一换一
题解:搜索+贪心
先求对于司机多少次连锁反应可以团灭
再求对于齐齐多少次连锁反应可以团灭
然后比较两个的次数
如果齐齐的次数<司机的次数,输出-1
否则,求齐齐用来极限一换一的连锁的那几个大炮,产生连锁反应,所损失的最小的大炮数,然后总数再减去损失数就是答案
求连锁反应的可以用搜索,对于每次的求的时候要标记,防止重复,就是求每一次的连锁反应可以影响多少个大炮
然后把求的连锁反应所影响的大炮的个数从小到大排序,取前司机团灭数个求和
时间复杂度: 实际要高于的,但是每次搜索有标记所以还是比较趋近的

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll MOD=1e9+7;
int num,w,numq,nump,qq[10000],pp[10000];
char q[10][110],p[10][110];
bool visq[10][110],visp[10][110];
void dfsp(int x,int y)
{
    if(visp[x][y]) 
        return;
    num++;
    visp[x][y]=1;
    for(int i=-1;i<=1;i++)
    {
        for(int j=-1;j<=1;j++)
        {
            if(i==j&&i==0) 
                continue;
            int nx=x+i,ny=y+j;
            if(nx<=0||ny<=0||nx>4||ny>w) 
                continue;
            if(p[nx][ny]=='*') 
                dfsp(nx,ny);
        }
    }
}
void dfsq(int x,int y)
{
    if(visq[x][y]) 
        return;
    num++;
    visq[x][y]=1;
    for(int i=-1;i<=1;i++)
    {
        for(int j=-1;j<=1;j++)
        {
            if(i==j&&i==0) 
                continue;
            int nx=x+i,ny=y+j;
            if(nx<=0||ny<=0||nx>4||ny>w) 
                continue;
            if(q[nx][ny]=='*') 
                dfsq(nx,ny);
        }
    }
}
int main()
{
    cin>>w;
    for(int i=1;i<=4;i++)
        for(int j=1;j<=w;j++) 
            cin>>p[i][j];
    for(int i=1;i<=4;i++)
        for(int j=1;j<=w;j++) 
            cin>>q[i][j];
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=w;j++)
        {
            if(p[i][j]=='*'&&!visp[i][j])
            {
                num=0;
                dfsp(i,j);
                pp[nump++]=num;
            }
        }
    }
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=w;j++)
        {
            if(q[i][j]=='*'&&!visq[i][j])
            {
                num=0;
                dfsq(i,j);
                qq[numq++]=num;
            }
        }
    }
    if(nump>numq) 
        printf("-1\n");
    else
    {
        int total=0;
        sort(qq,qq+numq);
        for(int i=0;i<numq;i++) 
            total+=qq[i];
        for(int i=0;i<nump-1;i++) 
            total-=qq[i];
        printf("%d\n",total);
    }
    return 0;
}