链接:

文章目录

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld

题目描述

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

输入描述:
第1行输入一个整数m,表示地图的宽度。
第2-5行,每行输入一串长度为m的字符串,代表司机的大炮部署。(大炮为"“号,空地为“.”号)
第6-9行,每行输入一串长度为m的字符串,代表齐齐的大炮部署。(大炮为”
"号,空地为“.”号)
数据保证:0<m≤100
输出描述:
输出一行,一个整数。代表摧毁所有司机的大炮后最多保留几门大炮。如果不能摧毁所有司机的大炮,则输出-1。
示例1
输入

3
...
.*.
..*
*..
*..
.**
...
*.*

输出

4

示例2
输入

3
*..
..*
...
...
...
...
.*.
...

输出

-1

题解:

炮弹的威力是以被打目标a为中心的3*3的波及区域,也就是以a的上下左右,以及四个斜方位置(九宫格,a在最中间)。
而且一个大炮会因另一个大炮的爆炸而引爆,同时产生一个九宫格,引爆范围内其他大炮
这样就可以根据大炮的位置划分成若干个连通块,而每个连通块内部只要一个被炮弹打中,整个连通块都会爆炸
用并查集就OK
但是因为双方是来回进攻,齐齐也会损失,我们又先进攻,而且每次司机只会打我们上次使用的大炮。我们要让齐齐损失最小,且司机完蛋,就将齐齐的连通块按照从小到大排列,依次对司机进行进攻
如果最后齐齐先别消灭就输出-1
代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e2 + 3;
int fa[8 * maxn];
int dis[8 * maxn];
int dxdy[8][2] = {
    {
   1, 1}, {
   1, 0}, 
					{
   1, -1}, {
   0, 1}, 
					{
   0, -1}, {
   -1, 1},
					 {
   -1, 0}, {
   -1, -1} 
				};
string s[8];
int playerB;
int playerA;
int num[maxn];
int sum;
int find(int x)
{
   
	if(fa[x]==x) return x;
	else fa[x] = find(fa[x]);
}
void unionn(int x, int y) {
   
    int a = find(x); 
	int b = find(y);
    if (a != b) 
	{
   
        fa[a] = b;
        dis[b] += dis[a];
    }
}
int main() {
   
	   memset(num, 0, sizeof(num));
    int m;
	scanf("%dis",&m); 
    for (int i = 0; i < 8; i++)
	{
   
        cin >> s[i];
        for (int j = 0; j < m; j++) 
		{
   
            fa[i * m + j] = i * m + j;
            dis[i * m + j] = 1;
        }
    }
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < m; j++)
            if ('*' == s[i][j])
                for (int k = 0; k < 8; k++) 
				{
   
                    int dx = i + dxdy[k][0];
                    int dy = j + dxdy[k][1];
                    if ( ( dx && dx <= 3 && i <= 3) || (dx >= 4 && dx <= 7 && i >= 4) )
					{
   
						if (dy && dy <= m - 1)
						{
   
							if ( s[dx][dy]=='*' )unionn(dx * m + dy, i * m + j);
						}//如果是齐齐的地盘 
                            
					}//如果没出界 

                        
                }

    for (int i = 0; i < 8; i++)
        for (int j = 0; j < m; j++)
        {
   
        	int w=i*m+j;
        	if ('*' == s[i][j] && fa[m] == m)
	            {
   
	            	if (i <= 3) playerB++;
	                else num[playerA++] = dis[i * m + j];
				}
		} 
            

    if (playerA < playerB)
	 {
   
        cout << -1 << endl;
        return 0;
    }
    
    sort(num, num + playerA);
    
 
    for (int i = playerB - 1; i <= playerA - 1; i++)
        sum += num[i];
        
    printf("%d\n",sum);
    return 0;
}