膜法记录(二进制枚举）s1050712899的博客-

传送门

题目描述

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

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

输出描述:
对每组测试数据输出一行，如果能消灭所有的敌人，就输出yes，否则输出no
示例1
输入

2
3 3 1 2
…*
.*.
…
4 4 3 1
…*
…
..
.*

输出

yes
no

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

思路：i用二进制表示，0表示此行不使用，1表示使用，所以0-(2^n-1)可以枚举出所有的情况（每一行是否使用消灭行线灭操作），i右移j位来找到i中有几个1，如果1的个数和a相等，然后遍历矩阵，如果(k,j)这个格子满足：第k行没有使用行消灭，该格子有敌人，就需要执行列消灭，所以c++，遍历结束之后，c<=b输出”yes”

AC代码

#include<bits/stdc++.h> using namespace std; const int maxn=1e6+100; const int inf=0x3f3f3f3f; string s[maxn]; int main() { int n,m,a,b,flag=0,t;      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++)//0001 0010 0011 0100......... { int r=0; for(int j=0;j<n;j++) if((i>>j)&1)r++; if(r!=a)continue; int c=0; for(int j=0;j<m;j++) for(int k=0;k<n;k++) if(s[k][j]=='*'&&!((i>>k)&1)) {              c++; break; } if(c<=b)flag=1; } if(flag)cout<<"yes"<<endl; else cout<<"no"<<endl; } system("pause"); return 0; }