nc14698 模拟战役题解连通块问题

忘是亡心i 2023-03-02 14:54 17阅读 0赞

模拟战役：[原题链接][Link 1]

##### 题目描述： #####

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

##### 输入描述： #####

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

##### 输出描述： #####

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

--------------------

##### 思路： #####

这是一个**连通块问题**，将所有能互相炸到的大炮看作一个连通块，分别计算司机和齐齐的连通块数量，并记录齐齐每个连通块中大炮的数量。按照题意，齐齐炸掉司机的一个连通块会失去自己的这个连通块，因此按照齐齐每个连通块中大炮的数量递增排序，先用数量少的连通块炸，剩余的大炮会尽可能的多。

能否炸完司机只需比较齐齐和司机的连通块数量，若齐齐的连通块数量大于等于司机的，就能炸完，若小于，就炸不完，直接输出-1即可。

求一个连通块时用dfs，记录齐齐每个连通块中大炮的数量只需用一个数组存储即可。

--------------------

##### 代码解析： #####

#include<iostream>
    #include<cstring>
    #include<vector>
    #include<algorithm>
    using namespace std;
    const int N = 110;
    
    char e1[5][N],e2[5][N];	//存两个地图
    bool vis[N][N];	//标记数组
    int m,cnt,sum;	//m是宽度，cnt是一个连通块中大炮数量的计数变量，sum是剩余大炮数量和
    vector<int> arr1,arr2;	//存各个连通块中大炮的数量
    int ne[8][2] = { { 1,0},{ -1,0},{ 0,1},{ 0,-1},{ 1,1},{ 1,-1},{ -1,1},{ -1,-1}};	//因为炸毁的是3*3的地方，也就相当于向8个方向扩展
    
    void dfs(int x,int y,char e[5][N])	//dfs连接大炮形成连通块
    { 
    	cnt++;	//多一个大炮计数+1
    	vis[x][y] = 1;	//标记此大炮
    	for(int i = 0;i < 8;i++)	//向8个方向扩展
    	{ 
    		int tx = x + ne[i][0];
    		int ty = y + ne[i][1];
    		if(tx < 0 || ty < 0 || tx >= 4 || ty >= m)	//边界判断
    			continue;
    		if(e[tx][ty] == '*' && vis[tx][ty] == 0)	//如果碰到大炮，再dfs扩展
    			dfs(tx,ty,e);
    	}
    }
    
    vector<int> cal(char e[5][N])
    { 
    	vector<int> arr;	//arr来存储个连通块的大炮数量
    	memset(vis,0,sizeof vis);	//重置vis数组
    	for(int i = 0;i < 4;i++)
    	{ 
    		for(int j = 0;j < m;j++)	//遍历地图每个点
    		{ 
    			if(e[i][j] == '*' && vis[i][j] == 0)	//如果是大炮，dfs扩展
    			{ 
    				cnt = 0;	//重置cnt
    				dfs(i,j,e);
    				arr.push_back(cnt);	//cnt入数组
    			}
    		}
    	}
    	return arr;	//返回数组
    }
    
    int main()
    { 
    	cin >> m;
    	for(int i = 0;i < 4;i++)
    		for(int j = 0;j < m;j++)
    			cin >> e1[i][j];	//注意，此题中先输入的是司机的地图
    	for(int i = 0;i < 4;i++)
    		for(int j = 0;j < m;j++)
    			cin >> e2[i][j];	//e2是齐齐的地图
    
    	arr1 = cal(e1);
    	arr2 = cal(e2);
     	sort(arr1.begin(),arr1.end());	//对齐齐的各连通块中大炮的数量排序
     	if(arr1.size() < arr2.size())	//如果齐齐的连通块比司机的少，无法炸完，直接输出-1
    		cout << -1 << endl;
    	else
    	{ 
    		for(int i = arr2.size()-1;i < arr1.size();i++)
    			sum += arr1[i];	//如果能炸完，取炸完后，剩余的数量加和
    		cout << sum << endl;
    	}
    			
    	return 0;
    }

[Link 1]: https://ac.nowcoder.com/acm/problem/14698