段大佬写的二进制压缩小白看不太懂。所以参考其他大佬的思路,用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; }