【蓝桥杯选拔赛真题50】C++简易炸弹超人第十四届蓝桥杯青少年创意编程大赛算法思维 C++编程选拔赛真题解析

C++简易炸弹超人

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、程序说明

五、运行结果

六、考点分析

七、推荐资料

C++简易炸弹超人

第十四届蓝桥杯青少年创意编程大赛C++选拔赛真题

一、题目要求

1、编程实现

有一块矩形游戏场地，场地被分成NxM的网格(4≤N≤100,4≤M≤10),其中一部分小方格是水域,另一部分小方格是陆地。为防御敌军攻击，玩家需要在游戏场地安置炸弹：

炸弹只能安置在陆地上;
每颗炸弹爆炸后，可以波及到炸弹所在的小方格，及相邻的上、下、左、右小方格;3.任意两颗炸弹爆炸后不能波及到同一个小方格。

请帮助玩家计算出如何安置炸弹，可以使炸弹波及到的范围最大，输出最多可以波及到的小方格数量。例如:N=4，M=4，网格中水域和陆地的情况如图1所示

这块4x4的矩形游戏场地最多可以波及到11个小方格，其他方案都不会优于这个结果
图中，蓝色区域代表水域，绿色区域代表陆地;安置炸弹的最优方案之一如图2所示;炸弹波及的范围如图3所示(黑色区域)。

2、输入输出

输入描述：第一行输入两个正整数N和M(4≤N≤100,4≤M≤10),分别表示网格的行数和列数，两个正整数之间以一个空格隔开。接下来输入N行，每行M个字符(字符只能是大写字母A或B)，A表示水域，B表示陆地，字符之间以一个空格隔开.

输出描述：只有一行，一个整数，即最多可以波及到的小方格数量

输入样例：

4 4
B A A A
A B A B
B A B B
A B A A

输出样例：

二、算法分析

从给定题目的初步分析可以看出，本题具有一定的复杂度和难度的
这题的核心还是在算法的设计，从题意可以得到，需要计算的是波及方格数量最多
这就需要用到我们的动态规划算法进行实现
实现的思路是：根据输入的每个方格的初始状态，遍历每个是陆地的方格，进行炸弹的放置，然后根据当前方格影响到的上下左右四个方格的状态，统计出符合要求的受影响方格的数量，最后返回最大值

三、程序编写

#include <iostream>
#include <vector>
using namespace std;
const int N = 105, M = 12;
int n, m, grid[N], f[2][M][M];
vector<int> s;
bool check(int s) { return !(s & s >> 1 || s & s >> 2); }
bool check2(int s) { return s & s >> 1; }
int count(int x, int s) {
  	int cnt = 0, flag = 0;
  	for (int i = 0; i < m; i++)
    	if (s >> i & 1) {
      		flag = 1;
      		if (x - 1 >= 1) cnt++;
      		if (x + 1 <= n) cnt++;
      		if (i - 1 >= 0) cnt++;
      		if (i + 1 < m) cnt++;
    	}
  	return cnt + flag;
}
int main() {
  	cin >> n >> m;
  	for (int i = 1; i <= n; i++)
    	for (int j = 0; j < m; j++) {
      		char x;
      		cin >> x;
      		if (x == 'A')
        		grid[i] += 1 << j;
    	}
  	for (int i = 0; i < 1 << m; i++)
    	if (check(i))
      		s.push_back(i); 
    //动态规划算法实现
  	for (int i = 1; i <= n + 2; i++)
    	for (int j = 0; j < int(s.size()); j++)     
      		for (int k = 0; k < int(s.size()); k++)   
        		for (int u = 0; u < int(s.size()); u++) {
          			int a = s[u], b = s[k], c = s[j];
          			if ((a & b) || (b & c) || (a & c))
            			continue;
			        if ((grid[i] & c) || (grid[i - 1] & b))
			            continue;
			        if (check2(a | b))
			            continue;
			        int cnt = i <= n ? count(i, c) : 0;
          			f[i & 1][j][k] = max(f[i & 1][j][k], f[(i - 1) & 1][k][u] + cnt);
        		}
  	cout << f[(n + 2) & 1][0][0] << endl;
  	return 0;
}

四、程序说明

首先需要导入输入输出流头文件和vector头文件
然后是引入std命名空间中的所有成员到当前的程序中，这样在当前的程序中就可以直接使用 std 命名空间中的所有成员，而不需要使用的时候在成员前面加上（std::）前缀
定义了常量N和M，分别表示网格的行数和列数
接下来定义了全局变量n、m，分别表示输入的网格的行数和列数
还定义了一个长度为N的一维数组grid，用于存储输入的网格
然后定义了一个长度为2的二维数组f，用于存储动态规划的状态
定义了一个vector容器s，用于存储合法的状态
接下来定义了三个辅助函数，分别是check函数用于检查状态是否合法（不相邻的位置均为空），check2函数用于检查状态是否存在相邻的位置为空，count函数用于计算每个状态下填充的单元格数量。
主函数里面先读取输入的行数n和列数m，通过一个嵌套的循环遍历网格的每个单元格，将'A'表示的单元格使用位运算转化为二进制数并存储到grid数组中
接下来通过一个循环遍历所有可能的状态，并通过check函数筛选出合法的状态，将其存储到s容器中
使用动态规划的思想来解决问题。定义一个三维数组f，其中f[i][j][k]表示前i行，以第j个状态结尾的行和以第k个状态结尾的行的最大合法方案数
接下来的四重循环分别遍历了前i行的每一种可能的两个状态，以及第i+1行的所有合法状态
在每次迭代中，计算了前i行和第i+1行的状态之间的限制条件，并根据限制条件更新f数组
其中，a、b、c分别表示第i+1行、第i行、第i-1行的状态。如果a和b之间或b和c之间或a和c之间存在重叠的1，那么就跳过该状态，因为不满足合法条件。如果第i+1行的状态与c重叠，或者第i行的状态与b重叠，那么也跳过该状态。如果a和b合并之后的状态中存在连续两个1，也跳过该状态
最后输出f[(n + 2) & 1][0][0]，即前n行以第0个状态结尾的方案的最大值
最后返回0，程序结束

本文作者：小兔子编程作者首页：https://blog.csdn.net/frank2102