每日一题 模拟战役

不仔细理解，害，看了半天就是连通块（你会不会这个算法和你能不能凑看出来是两码事）
3*3的规模 在大炮的外围一圈内如果也有大炮就会波及，此时就连通起来了
既然如此可以用dfs找出各个连通块及其所含有的大炮数量
当然由于小齐先手攻击 它所要面对的司令的连通块个数减一（当然最后小齐炮的个数为0，虽说他为先手，没炮怎么打（wawa大哭））所以只要小齐的连通块个数大于等于司令的就可以
最后结果来贪心 小齐剩的的炮要多，则用含有少的炮的连通块抵消司令的连通块

#include<bits/stdc++.h>
using namespace std;
char a[10][105];
int l[8]={0,0,1,-1,-1,-1,1,1};///行
int r[8]={1,-1,0,0,1,-1,-1,1};///列 
int M[807];///司令
int N[808];///小齐
int vis[10][105];///标记位
int cnt_1=1;
int cnt_2=1;
int m;
bool check_1(int w,int q)///越界洞察
{
   if (w<0||w>=4||q<0||q>=m)
     return false;
   return true;
}
bool check_2(int w,int q)
{
   if (w<4||w>=8||q<0||q>=m)
     return false;
   return true;
}
void dfs_1(int w,int q)///司令
{
  vis[w][q]=1;
  for (int i=0;i<8;++i)///查找周围3*3的范围
  { 
    if (!vis[w+l[i]][q+r[i]]&&a[w+l[i]][q+r[i]]=='*'&&check_1(w+l[i],q+r[i]))///先查是否越界，再执行，否则还得退回来（开始就是被这里wa到了）
    {
      ++cnt_1;
      dfs_1(w+l[i],q+r[i]);
    }
  }
}
void dfs_2(int w,int q)
{

  vis[w][q]=1;
  for (int i=0;i<8;++i)
  {
    if (!vis[w+l[i]][q+r[i]]&&a[w+l[i]][q+r[i]]=='*'&&check_2(w+l[i],q+r[i]))
    {

      ++cnt_2;
      dfs_2(w+l[i],q+r[i]);
    }
  }
}
int main()
{
  scanf("%d",&m);
  memset(vis,0,sizeof(vis));
  for (int i=0;i<8;++i)
  {
    for (int j=0;j<m;++j)
    {
      cin>>a[i][j];
    }
  }
  int h=0;
  for (int i=0;i<4;++i)
  {
    for (int j=0;j<m;++j)
    {
      if (!vis[i][j]&&a[i][j]=='*')
      {  
         dfs_1(i,j);
         M[h++]=cnt_1;
         cnt_1=1;
      }
    }
  }
  int s=0;
  for (int i=4;i<8;++i)
  {
    for (int j=0;j<m;++j)
    {
      if (!vis[i][j]&&a[i][j]=='*')
      {  
         dfs_2(i,j);
         N[s++]=cnt_2;
         cnt_2=1;
      }
    }
  }
  sort(N,N+s);
  int ans=0;
  if (h>s)
  {
    printf("-1\n");
    return 0;
  }
  for (int i=h-1;i<s;++i)///用前h-1个连通块抵消司令的，这里他还有炮
  ///记得区分h>s而为什么不是h>s+1因为最后没炮了，就无法先手开炮
  {
    ans+=N[i];
  }
  printf("%d\n",ans);
  return 0;
}