由于行的数少,所以暴力考虑删除行的方法2^n,然后看剩下的列是否符合要求mn
由于后面mn,所以我们只考虑删行机会全部用完的方法
如果剩下需要删除的列<=删列机会,就找到方法break
这里用二进制数来压缩方法
时间极端:
情况一:25*1e5*5
情况二:220*+C(20,10)1e5*20=1e10--------------出题人应该没有出n=20,a=10,m=1e5的数据😅
#include<bits/stdc++.h>
using namespace std;
const int N=30;

string s[N];
int t,n,m,a,b,flag,r,c;

int main(){
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        cin>>n>>m>>a>>b;
        flag=0;
        for(int i=0;i<n;i++) cin>>s[i];
        for(int i=0;i<(1<<n);i++){//i记录的是消灭行情况,要从0开始,有行0机会情况
            r=0;
            for(int j=0;j<n;j++){
                if((i>>j)&1) r++;
            }
            if(r!=a) continue;
            c=0;
            for(int j=0;j<m;j++){
                for(int k=0;k<n;k++){
                    if(!((i>>k)&1)&&s[k][j]=='*') {
                        c++; break;
                    }
                }
            }
            if(c<=b){
                flag=1; break;//找到方法
            }
        }
        if(flag) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}