模拟战役

题意：给出一个整数m,再给出8行字符串，前4行为司机基地情况，后四行为齐齐基地情况，求齐齐在摧毁司机全部大炮后最多剩多少门大炮？（无法全部摧毁司机大炮则输出-1）

思路：dfs求出司机基地有多少个大炮连通块，再用dfs求出齐齐每一个大炮连通块的大炮个数并保存，由于保存最多的大炮，使用的大炮所在连通块在下次司机的攻击下会被摧毁，所以齐齐首先使用大炮连通块的大炮个数最少的攻击司机基地大炮。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

char s[15][1005], b[15][1005], dx[9]={1,1,1,0,0,0,-1,-1,-1}, dy[9]={1,0,-1,1,0,-1,1,0,-1};
int m;
void dfs(int x,int y)
{
    s[x][y]='.';
    for(int i=0;i<9;i++)
    {
        int x2=x+dx[i], y2=y+dy[i];
        if(x2<4&&x2>=0&&y2<m&&y2>=0&&s[x2][y2]=='*')
        {
            dfs(x2,y2);
        }
    }
}

int dfs1(int x,int y)
{
    int z=1;
    b[x][y]='.';
    for(int i=0;i<9;i++)
    {
        int x2=x+dx[i], y2=y+dy[i];
        if(x2<4&&x2>=0&&y2<m&&y2>=0&&b[x2][y2]=='*')
        {
            z=z+dfs1(x2,y2);
        }
    }
    return z;
}


int a[10005], ji=0;

int main()
{
    scanf("%d",&m);
    for(int i=0; i<8; i++)
    {
        if(i<4)
            scanf("%s",s[i]);
        else
            scanf("%s",b[i-4]);
    }
    int z=0;
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(s[i][j]=='*')
            {
                dfs(i,j);
                z++;
            }
        }
    }
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(b[i][j]=='*')
            {
                a[ji++]=dfs1(i,j);
            }
        }
    }
    if(z>ji)
    {
        printf("-1\n");
    }
    else
    {
        sort(a,a+ji);
        int ans=0;
        for(int i=max(0,z-1);i<ji;i++)
        {
            ans+=a[i];
        }
        printf("%d\n",ans);
    }
    return 0;
}