思路：在原矩阵的条件下检查，遍历每一行，检查该行是否可以丢掉，如果可以先丢掉，继续遍历，不断更新最小值。边界条件是剩余任何一 行都不能再丢 了。
#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<cstdlib> #include<cstring> using namespace std; int m,n,minm,sum,s,flag; char test[501][16]; //输入矩阵 int H[501]={0}; //标记是否已经处理过 int check(int k){ //检查如果丢掉第K行是否满足条件 for(int i=0;i<n;i++){ sum=0; for(int j=0;j<m;j++) if(j!=k&&H[j]!=1) sum+=test[j][i]-'0'; //列求和 if(!sum) return 0; } return 1; } void dfs(int record){ s=0; minm=min(minm,record); //找最小值 for(int i=0;i<m;i++){ //边界条件 s+=check(i);} if(!s) return; for(int i=0;i<m;i++) if(H[i]!=1&&check(i)){ H[i]=1,record--; //标记 flag=1; dfs(record); //往下搜索 H[i]=0,record++; //恢复原条件 } } int main() { int T; cin>>T; while(T--){ scanf("%d%d",&n,&m); minm=m; memset(H,0,sizeof(H)); for(int i=0;i<m;i++){ scanf("%s",test[i]); } flag=0; //是否进行过操作 dfs(m); if(flag) printf("%d\n",minm); else printf("-1\n"); } return 0; }