段大佬写的二进制压缩小白看不太懂。所以参考其他大佬的思路,用dfs暴力搜索写了一个。
思路:一开始所有的行都不标记,然后再回溯的时候依次遍历所有的情况(依次标记所有的组合),当所有的行blast都用完时并且列blast小于要消除的列时,说明可以消除完,返回true。其他情况下都为false。

#include<iostream>
#include<math.h>
#include<cstring>
using namespace std;
//用行blast去消去列最多的行,剩下最少的列,然后看列blast够不够就可以。
const int maxn=100001;
int visit[maxn];//记录行是否访问过
char g[21][100001];//用图来存储 
int n,m,a,b;
bool flag=false;
bool check(){//用来判断是否列blast小于需要消除的列(比较费时) 
    int res=0;//记录要消除的列数 
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(!visit[j]&&g[j][i]=='*'){
                res++;
                break;    
            }
        }
    }
    if(res>b)return false;//如果列数>列blast说明消除不完,返回false 
    else return true;
}
void dfs(int now,int already){//now是当前行,already是已经消除的行数 
    if(now==n){
        if(already==a&&check())//判断是否所有的行blast都用完了,不用白不用(减少check的次数) 
            flag=true;
        return;
    }if(flag)return ;//剪枝 
    visit[now]=0;
    dfs(now+1,already);//不消除本行,在回溯的时候依次组合所有行
    if(flag)return ;//剪枝 
    if(already<a){
        visit[now]=1;
        dfs(now+1,already+1);//回溯时候依次组合所有情况 
    } 
} 
int main(){
    int t;
    cin>>t;
    while(t--){
        flag=false;
        cin>>n>>m>>a>>b;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>g[i][j];
            }
        }
        dfs(0,0);
        if(flag)cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    } 
    return 0;
}