题解 | 小心火烛的歪

/*本题目由于限制的数量比较少，行与列都只有7所以最多只有128种方案直接按照二进制存放的规则进行穷举，由于本人是新手小白，刚开始学习，本次代码的内容为摘抄加自身理解，如果有问题还请多多指教*/



#include <stdio.h>

typedef  unsigned long long ull;
ull grid,plan[10];
int plan_id[10];
int n,m,q;
int cnt;

ull mask(char mat[10][10]){			//将二维数组转化为掩码
    ull a=0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (mat[i][j]=='1') {
                a|=1ull<<(i*m+j);
            }
        }
    }
    return a;
}


int main() {
    scanf("%d %d %d", &n, &m,&q);
    char a[10][10];
    for (int i=0; i<n; i++) {
        scanf("%s",a[i]);
    }
    grid=mask(a);				//将草地转化为掩码
    cnt =0;
    ull t=(~grid)&((1ull<<(n*m))-1);			//空地变成1，杂物变成0，只保留n*m位
    for (int i=0; i<q; i++) {
        for (int j=0; j<n; j++) {				//读取当前计划的第n行
        scanf("%s",a[j]);
        }
        ull b=mask(a);

        if ((b&grid)==0) {					//判断该计划是否合理，按位与空地，如果不为零则说明不合法
            plan_id[cnt]=i+1;				//记录合法数组的编号
            plan[cnt++]=b;					//将合法计划的掩码进行保存
        }
    }

    if (t==0) {								//如果空地全是杂物则直接输出0
        printf("0\n");
        return 0;
    }
//暴力穷举
    for (int i=1; i<=cnt; i++) {			//循环遍历所有合理的计划，从只选一种计划开始
        for (int j=0; j<(1<<cnt);j++) {
            int b=__builtin_popcount(j);		//获取目前方案选择的计划数，b=j里含有1的个数；
            if (b!=i) {						//如果b不等于我们需要的计划数，那就舍弃；
                continue;
            }

            ull c=0;
            for (int k=0; k<cnt; k++) {		//如果计划数遍历到的最小计划数，则开始判断计划相加是否满足条件
                if((j&(1<<k))){
                    c|=plan[k];				//按位或可以将计划中所有的1放在一起
                }
            }
            if (c==t) {						//如果计划合起来能填充整个空地则开始输出
                printf("%d\n",i);
                for (int k=0; k<cnt; k++) {
                    if ((j&(1<<k))) {
                        printf("%d ",plan_id[k]);
                    }
                }
                return 0;					//此时我们的计划数一定是最小的所以直接结束程序。
            }
        }
    }
    
        
    printf("-1");							//如果没有找到就说明不存在方案则直接输出-1
    return 0;
}