模拟战役

题目链接：https://ac.nowcoder.com/acm/problem/14698

题目描述

齐齐和司机在玩单机游戏《红色警戒IV》，现在他们的游戏地图被划分成一个n*m的方格地图。齐齐的基地在最上方的4行格内，司机的基地在最下方的4行格内。他们只有一种攻击方式：远程大炮，相关属性如下：
1、 大炮可以打到地图的任意一个位置。
2、 双方每次必须动用本方的一门大炮攻击，齐齐先手，双方交替进行攻击。
3、 一方大炮只能攻击另一方大炮，不能攻击本方或强制攻击未获得视野的地区。
4、 被一方大炮击中的另一方大炮会产生以攻击点为中心的33的波及区域，波及区域内如果有其他大炮则也会产生33的波及区域。
5、 两方的基地相距很远，所以不存在攻打敌方大炮时波及到本方大炮的情况。
齐齐偷偷开了“间谍卫星”，所以他能看到司机的大炮部署，司机则无视野。但如果齐齐做出攻击，司机会立即获取到发动攻击的大炮的视野，并在回合开始时动用大炮（如果存在的话）将其摧毁（摧毁后可能产生的连锁不计入视野）。
现在给出齐齐和司机的大炮部署，问齐齐在选择最优的策略下，在摧毁所有司机的大炮后可以保留最多几门本方大炮。

输入描述

第1行输入一个整数m，表示地图的宽度。
第2-5行，每行输入一串长度为m的字符串，代表司机的大炮部署。（大炮为”*“号，空地为“.”号）
第6-9行，每行输入一串长度为m的字符串，代表齐齐的大炮部署。（大炮为”*“号，空地为“.”号）
数据保证：0<m≤100

输出描述

输出一行，一个整数。代表摧毁所有司机的大炮后最多保留几门大炮。如果不能摧毁所有司机的大炮，则输出-1。

示例

输入

3
…
.*.
..*
*..
*..
.**
…
*.*

输出

4

分析

本题为连通块问题，此处采用深搜解决连通块。 由题意得每门大炮之间有3*3的空间约束，满足该约束条件的所有大炮形成一个块。我们可以从一个块出发向周围8个块进行深度搜索，从而得知一个块的大炮数目。按照题意，齐齐某个块内的大炮向司机某个块中的大炮发起进攻，结果是两个块都将消失。由此我们便可想到，若齐齐的块数目小于司机，则齐齐输，否则，我们便选择使用齐齐的大炮数目小的块去进攻从而留下数目大的块。
因此，在得到两人连通块数据后进行排序，按照上述思路处理即可。

AC代码

---

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int m;
bool base1[4][100];     //记录司机部署
bool base2[4][100];     //记录齐齐部署
int cnt;
bool visited[4][100];   //记录是否搜索过某个位置
int dir[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1},{1,1},{1,-1},{-1,-1},{-1,1}}; //试探的八个方向
void dfs1(int x, int y)
{
    cnt++;
    visited[x][y] = true;
    for (int i = 0; i < 8; i++)
    {
        int newx = x + dir[i][0];
        int newy = y + dir[i][1];
        if (newx < 0 || newx >= 4 || newy < 0 || newy >= m)
            continue;
        if (visited[newx][newy])
            continue;
        if(base1[newx][newy])
            dfs1(newx,newy);
    }
}
void dfs2(int x, int y)
{
    cnt++;
    visited[x][y] = true;
    for (int i = 0; i < 8; i++)
    {
        int newx = x + dir[i][0];
        int newy = y + dir[i][1];
        if (newx < 0 || newx >= 4 || newy < 0 || newy >= m)
            continue;
        if (visited[newx][newy])
            continue;
        if(base2[newx][newy])
            dfs2(newx,newy);
    }
}
int main()
{
    cin >> m;
    cin.get();
 
    for (int i = 0; i < 4; i++)
    {
        string temp;
        getline(cin, temp);
        for (int j = 0; j < m; j++)
        {
            if (temp[j] == '*')
                base1[i][j] = true;
            else
                base1[i][j] = false;
        }
    }
    for (int i = 0; i < 4; i++)
    {
        string temp;
        getline(cin, temp);
        for (int j = 0; j < m; j++)
        {
            if (temp[j] == '*')
                base2[i][j] = true;
            else
                base2[i][j] = false;
        }
    }
 
    memset(visited,0,sizeof(visited));
    vector<int> sum1;   //储存各个连通块内大炮的数量
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(base1[i][j] && !visited[i][j])
            {
                cnt=0;
                dfs1(i,j);
                sum1.push_back(cnt);
            }
        }
    }
 
    memset(visited,0,sizeof(visited));
    vector<int> sum2;
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(base2[i][j] && !visited[i][j])
            {
                cnt=0;
                dfs2(i,j);
                sum2.push_back(cnt);
            }
        }
    }
    sort(sum1.begin(),sum1.end());
    sort(sum2.begin(),sum2.end());
    if(sum1.size()>sum2.size())
        cout << -1 << endl;
    else
    {
        int sum=0;
        for(int i=sum1.size()-1;i<sum2.size();i++)
            sum+=sum2[i];
        cout << sum << endl;
    }
    return 0;
}