模拟战役题解搜索

这道题其实就是找一个连通块的个数，就是直接找八个方向，然后比较两个人的3*3范围的扩散开连通块的个数，利用DFS都跑一下两个人的连通块个数 ，然后就是直接贪心一下，用齐齐连通块里面个数最少的去攻打司机，最后剩下的连通块加起来就是ans了；

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
char ans[300][300];
int ans1[maxx],ans2[maxx];
int dd[][2]={1,0,-1,0,0,1,0,-1,-1,-1,-1,1,1,-1,1,1};
int num;
int m;
void dfs(int x,int y,int k){
    if(ans[x][y]=='.')  return ;
    ans[x][y]='.',++num;
    for(int i=0;i<8;i++){
        int xx=x+dd[i][0],yy=y+dd[i][1];
        if(xx>=0+k&&xx<4+k&&yy>=0&&yy<m){
            dfs(xx,yy,k);
        }
    }
}
int main()
{
    fio;
    cin>>m;
   for(int i=0;i<8;i++) cin>>ans[i];
    for(int i=0;i<4;i++){
        for(int j=0;j<m;j++){
            if(ans[i][j]=='*'){
                num=0;
                dfs(i,j,0);
                ans1[++ans1[0]]=num;
            }
        }
    }
    for(int i=4;i<8;i++){
        for(int j=0;j<m;j++){
            if(ans[i][j]=='*'){
                num=0;
                dfs(i,j,4);
                ans2[++ans2[0]]=num;
            }
        }
    }
    if(ans1[0]>ans2[0]) cout<<-1;
    else
    {
        sort(ans2+1,ans2+ans2[0]+1);
        int sum=0;
        //cout<<ans1[0]<<" "<<ans2[0]<<endl;
        for(int i=ans1[0];i<=ans2[0];i++){
            sum+=ans2[i];

        }
        cout<<sum;
    }
    return 0;

}