【牛客小白月赛23 A】膜法记录 （二进制枚举）

【题目传送门】

题目描述：

牛牛最近在玩一款叫做《膜法记录》的游戏，这个游戏的机制是这样的： 在一局游戏中，所有的敌人都排布在一个 n{n}n 行 m{m}m 列的网格中，牛牛指挥着他的魔法少女对敌人进行攻击。 攻击有两种类型：行blast，列blast 行blast能消灭一整行的敌人，列blast能消灭一整列的敌人 牛牛总共能够释放 a{a}a 次行blast，b{b}b 次列blast 给定某局游戏的初始局面，请问牛牛能否将敌人全歼？

输入描述:

第一行包含一个正整数T，表示测试数据组数，接下来是T组测试数据每组测试数据的第一行有四个正整数 n,m,a,b接下来有n{n}n行，每行是一个长度为m的字符串，第i行第j列的字符如果是 * 则说明这里有一个敌人，如果是 . 说明这里没有

输出描述:

对每组测试数据输出一行，如果能消灭所有的敌人，就输出yes，否则输出no

说明

第一个样例，我可以在第一行放一个行blast，然后前两列都放一个列blast，就把敌人给全歼了。第二个样例，我不管怎么安排攻击策略，都没法全歼敌人

备注:

分析：

这道题的n很小，只有20，我们可以利用二进制数来枚举可操作的行，我们可以认为1是对行操作，0是不操作；比如n=4时，若对3,4行操作对应的二进制数表示为1100。
由此我们对 0到2^n-1 （0表示都不操作，2^n-1表示的二进制数每一位都为1，即表示对n行都操作）范围内的数进行遍历，即枚举各种可操作行的组合。
然后再对整个矩阵进行遍历，选出来没有被行操作过得敌人，让列进行操作,如果 列操作 的次数小于题目中给定的次数，即满足，反之不满足。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+100;
string s[N];//字符串数组
int main() {int n,m,a,b,t;int flag;cin>>t;while(t--){flag=0;cin>>n>>m>>a>>b;for(int i=0;i<n;i++) cin>>s[i];for(int i=0;i<(1<<n);i++)//枚举0-2^n-1范围内的数，即枚举各种组合；{int x=0;for(int j=0;j<n;j++)if((i>>j)&1) x++;//判断有几个位有1，即对 几行 操作if(x!=a) continue;int y=0;for(int j=0;j<m;j++)for(int k=0;k<n;k++)if(s[k][j]=='*'&&!((i>>k)&1))//判断一下这个行有没有操作过，如果行操作过，就不用列操作了{y++;break;//这一列消灭完了，就跳出这一列到下一列；}if(y<=b) flag=1;}if(flag) cout<<"yes"<<endl;else cout<<"no"<<endl;}return 0;
}

six day~