牛客小白月赛23A——膜法记录

膜法记录

https://ac.nowcoder.com/acm/contest/4784/A

网址：https://ac.nowcoder.com/acm/contest/4784/A

题目描述

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

输入描述:

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

输出描述:

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

输入

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

输出

yes
no

说明

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

备注:

要么1≤T≤10^5,1≤n≤5,1≤∑m≤10^5
要么T=1,1≤n≤20,1≤m≤10^5
对于以上两种情况都满足:1≤a≤n,1≤b≤m

题解：

由于这道题中的n比较小，可以暴力求解。
首先如果只有s列有敌人，且s<=a;或者只有s1行有敌人,且s1<=b;都输出yes;
如果不是再另行讨论
dfs列，删除a列之后，遍历记录有s2行有敌人，如果s1<=b,则输出yes;
如果dfs所有可能组合之后，仍旧没有一种情况是s2<=b,那么输出no

AC代码：

#include<iostream>
#include<cstring>
using namespace std;
char c[20][100000];
int t,n,m,a,b;
int f[20];
int p[20],l[100000];
int h[100000];
int plug=0;
int sum=0;
void dfs(int x,int k){
    if(plug) return ;
    if(x==0){
        sum++;
        memset(h,0,sizeof(h));
        for(int i=0;i<n;i++){
            if(f[i]){
                for(int j=0;j<m;j++){
                    if(c[i][j]!='.') h[j]++;
                }
            }
        }
        int s=0;
        for(int i=0;i<m;i++)
            if(l[i]-h[i]) s++;
        if(s<=b){
            plug=1;
        } 
        return ;
    }
    for(int i=k;i<n;i++){
        if(p[i]){
            p[i]=0;
            f[i]=1;
            dfs(x-1,i+1);
            p[i]=1;
            f[i]=0;
        }
    }
}
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m>>a>>b;
        memset(l,0,sizeof(l));
        memset(p,0,sizeof(p));
        memset(f,0,sizeof(f));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>c[i][j];
                if(c[i][j]!='.') p[i]++,l[j]++;
            }
        }
        int s=0;
        for(int i=0;i<n;i++)
            if(p[i]) s++;
        if(a>=s) {
            cout<<"yes"<<endl;
            continue;
        }
        s=0;
        for(int i=0;i<m;i++)
            if(l[i]) s++;
        if(b>=s){
            cout<<"yes"<<endl;
            continue;
        }
        plug=0;
        dfs(a,0);
        if(plug) cout<<"yes"<<endl;
        else cout<<"no"<<endl; 
    }
    return 0;
}