简易炸弹超人 题解----LQB2023中级组选拔赛

一、题目描述

有一块矩形游戏场地，场地被分成 N* M 的网格(4>N<100，4>M<10)其中一部分小方格水域，另一部分小方格是陆地。
为防御敌军攻击，玩家需要在游戏场地安置炸弹:
1.炸弹只能安置在陆地上;
2.每颗炸弹爆炸后，可以波及到炸弹所在的小方格，及相邻的上、下、左、右小方格;
3.任意两颗炸弹爆炸后不能波及到同一个小方格
请帮助玩家计算出如何安置炸弹，可以使炸弹波及到的范围最大，输出最多可以波及到的小方格数量。
例如:N=4，M=4，网格中水域和陆地的情况如图1所示:

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

输入

第一行输入两个正整数 N和M (4

输出

输出一个整数，表示最多可以波及到的小方格数量

样例输入 

44
BAAA
ABAB
BABB
ABAA

样例输出 

11

二、分析一波

根据题目我们可以得出以下此图：

 备注：图中红色的为炸弹，黄色为波及范围，橙色是不能放置下一个炸弹的位置

当时在测试的我，觉得直接用DFS做即可，但没把代码打完。

逻辑和实现

我们用二进制来标记该位置是否为水域*（0是陆地，1是水）
是否有炸弹也用二进制（1表示安装过了，0表示没有）
SO，这里用俩数组记录该位置，G[i]用来记录该位置是否为水域，S[i]用来记录该位置是否安装过炸弹。
SO这里又要使用“与”运算（&）和“移位”（<<和>>）and 二进制中的常规运算
这里就不讲了，自己可以查：基础的二进制运算（我是小白，也不太会）

回归正题：
当G[i]&s[i]=0时就符合题意
如何判断某一行的状态是否合法，状态中不能有相邻1的间隔小于2:记某一行的状态的为s，只要保证每一个1右边第一一个位置和第二个位置不为1，即可，即s&s>> 1和s&s>> 2均为0。

状态定义

状态表示:
f[i][j][k]：第i行炸弹安装状态为j，且第i-1行的状态为k，能波及到的最大格子数
状态转移:
若第i-2层的状态是u，那么结果就是f[i- 1][k][u] + count(i,c),其中count(i,c)表示第i行的状态为c时可以波及到的小方格数量。
SO，状态转移方程就是: f[i][j][k] = max{f[i][j][k], f[i-1][k][u]+ count(i,c)}。
优化原因：如果不优化，每行最多有2的M次方个状态，会超时，AND空间复杂O为(N*2的M次方*2的M次方），会爆，SO只能搞滚动数组。

接着，都分析到这了，上代码~~~~~~

#include 
#include 
using namespace std;
const int N=110,M=1 << 10;
int n,m,g[N],cnt[M],f[2][M][M];
vector s, h[M];
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>i&1){flag=1;if(x-1>=1) cnt++;if (x+1<=n) cnt++;if(i-1>=0) cnt++;if (i+1>n>>m;for(int i=1;i<=n;i++){for(int j=0;j>x;if(x=='A') g[i]+= 1 <

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！