NC14698 模拟战役

题目地址：

https://ac.nowcoder.com/acm/problem/14698

基本思路：

主要难点在我们要先理清楚题意，基本意思是齐齐和司机每次都能消灭到对方一个联通块，齐齐先手要让最后自己剩下的大炮尽量多，所以关键是这句话：如果齐齐做出攻击，司机会立即获取到发动攻击的大炮的视野，并在回合开始时动用大炮（如果存在的话）将其摧毁，那么这句话就相当于说齐齐有能力决定对方消灭自己哪几个联通块，所以我们只要统计一下在司机的联通块被消灭完的情况下，齐齐这边的能剩下几个连通块，然后贪心的取大炮最多的联通块剩下就是了。求联通块方面可以使用dfs或者其他各种方法解决。

ps.注意一下题目前面说齐齐的基地在上方4行格，但是输入的时候却在下面......

参考代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
const int maxm = 150;
int m;
char a[10][maxm];
int d[8][2] = {{1,0},{0,1},{-1,0},{0,-1},{1,-1},{-1,1},{1,1},{-1,-1}};
bool vis1[10][maxm],vis2[10][maxm];
int cnt;
void dfs1(int x,int y){//dfs填充连通块;
  vis1[x][y] = true; cnt++;
  for(int i = 0 ; i < 8 ; i++){
    int nx = x + d[i][0],ny = y + d[i][1];
    if(nx >= 1 && nx <= 4 && ny >= 1 && ny <= m && !vis1[nx][ny] && a[nx][ny] == '*') dfs1(nx,ny);
  }
}
void dfs2(int x,int y){//同上
  vis2[x][y] = true; cnt++;
  for(int i = 0 ; i < 8 ; i++){
    int nx = x + d[i][0],ny = y + d[i][1];
    if(nx >= 5 && nx <= 8 && ny >= 1 && ny <= m && !vis2[nx][ny] && a[nx][ny] == '*') dfs2(nx,ny);
  }
}
vector<int> res1,res2;
void solve(){
  //统计司机的连通块数,和每个连通块包含的大炮数;
  mset(vis1,false);
  rep(i,1,4){
    rep(j,1,m) if( !vis1[i][j] && a[i][j] == '*'){
      cnt = 0;
      dfs1(i,j);
      res1.push_back(cnt);
    }
  }
  //统计齐齐的连通块数,和每个连通块包含的大炮数;
  mset(vis2,false);
  cnt = 0;
  rep(i,5,8){
    rep(j,1,m) if( !vis2[i][j] && a[i][j] == '*'){
      cnt = 0;
      dfs2(i,j);
      res2.push_back(cnt);
    }
  }
}
signed main() {
  IO;
  cin >> m;
  rep(i,1,8){
    rep(j,1,m) cin >> a[i][j];
  }
  solve();
  int k1 = (int)res1.size(),k2 = (int)res2.size();
  if(k2 <= k1 - 1){//这种情况代表不能消灭司机;
    cout << -1 << '\n';
  }else{
    int ans = 0;
    int tmp = k2 + 1 - k1;//剩下的联通块数;
    sort(res2.begin(), res2.end(),greater<>());
    //贪心给炮多的连通块;
    for(int i = 0 ; i < tmp ; i++) ans += res2[i];
      cout << ans << '\n';
  }
  return 0;
}