二进制枚举（三）

#include <stdio.h>
#include <string.h>
int n;
char a[5][5];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int judge(int x)    // 判断计算二进制数表示的状态x中的1位是否都能建造碉堡，如不能返回1；否则返回可建造的碉堡个数
{
    char b[5][5];
    int c[20], tot = 0;              // 分别保存碉堡建造的位置和总个数
    memcpy(b, a, sizeof(a));
    int i,j;
    for (i = 0; i < n * n; i++)      // 在二进制状态x中的1位建造碉堡
    {
        if (x & (1 << i))
        {
            int xx = i / n;
            int yy = i % n;
            if (b[xx][yy] == 'X')     // 剪枝，如果碉堡建造在墙上，直接返回-1
                return -1;
            b[xx][yy] = 'a';         // 建造碉堡
            c[tot++] = i;
        }
    }
    for (i = 0; i < tot; i++)        // 看建造的每个碉堡是否可行
    {
        int x1 = c[i] / n;
        int y1 = c[i] % n;
        for (j = 0; j < 4; j++)      // 四个方向遍历
        {
            int x2 = x1 + dir[j][0];
            int y2 = y1 + dir[j][1];
            while(x2 >= 0 && x2 < n && y2 >= 0 && y2 < n)// 控制边界
            {
                if(b[x2][y2] == 'X')   break;      // 碰到墙跳出循环
                if(b[x2][y2] == 'a')   return -1;  // 碰到另一个碉堡'a'，不可行
                x2 += dir[j][0];                   // 继续往这方向遍历
                y2 += dir[j][1];
            }
        }
    }
    return tot;
}
int main()
{
    while(scanf("%d",&n) && n!=0)
    {
        int ans = 0;
        int i;
        for (i = 0; i < n; i++)
            scanf("%s",a[i]);
        for (i = 0; i < (1 << (n * n)); i++)       // 二进制枚举地图各点建造碉堡的全部组合
        {
            int cnt=judge(i);
            if (cnt>ans) ans = cnt;
        }
        printf("%dn",ans);
    }
    return 0;
}

#include <stdio.h>
int main()
{
    char a[21][21],b[21][21];
    int na,ma,nb,mb;
    scanf("%d%d",&na,&ma);
    int i,j,k;
    for (i=0; i<na; i++)
        scanf("%s",a[i]);
    scanf("%d%d",&nb,&mb);
    for (i=0; i<nb; i++)
        scanf("%s",b[i]);
    int flag=0,h[21];
    for (k=0; k<(1<<nb); k++)              // 二进制枚举B矩阵的行组合
    {
        int cnt=0;
        for (j =0; j<nb; j++)              // 遍历二进制的每一位
        {
            if (k & (1 << j))              // 判断二进制第j位是否为1，若为1，表示行选中
                h[cnt++]=j;                // 如果第j个元素选中，则记录选中的行号
        }
        if (cnt==na)                       // 矩阵B选中的行数正好是矩阵A的行数na
        {
            int st=0;                      // 矩阵B中可以挑选的起始列号
            while (st<=mb-ma)
            {
                int cola=0,ff=1;
                for (i=st; i<mb; i++)      // 从矩阵B的起始列到最后列中看能否找到矩阵A的所有列
                {
                    ff=1;
                    for (j=0; j<na; j++)   // 矩阵A中各行的当前列在矩阵B选中行的某列是否一致
                        if(a[j][cola]!=b[h[j]][i])
                        {
                            ff=0;
                            break;
                        }
                    if (ff) cola++;
                    if (cola==ma) break;   // A矩阵的ma列全部可在B矩阵中找到
                }
                if (cola==ma)              // A矩阵的ma列全部可在B矩阵中找到
                {
                    flag=1;
                    break;
                }
                st++;                      // 当前起始列不恰当，将下一列作为起始列，重新找
            }
            if (flag==1) break;            // 已找到答案，退出循环
        }
    }
    if (flag) printf("Yesn");
    else      printf("Non");
    return 0;
}

#include <stdio.h>
#include <string.h>
int main()
{
    int m,n;
    while (scanf("%d%d", &m, &n)!=EOF){
        int col[301];
        int i,j,x,flag = 0;
        memset(col, 0, sizeof(col));
        for (i=0; i<m; i ++){                       // 输入时预处理，将每列中各行0、1组成的二进制数转换为十进制数保存到数组col中
            for (j=0; j<n; j++){
                scanf("%d",&x);
                if (x==1) col[j] += (1 << i);
                if (i==m-1 && col[j]==0) flag = 1;  // 若每列1的个数为0，显然不可能
            }
        }
        if (flag){
            printf("It is impossiblen");
            continue;
        }
        for (i=1; i<(1<<m); i++){                   // 用二进制枚举，对各行的组合进行选择
            for (j = 0; j < n; j ++){
                int t = col[j] & i;
                if (t==0 || (t & (t-1))) {
                    break;
                }
            }
            if (j==n) {flag = 1; break; }
        }
        if (flag == 0)
           printf("It is impossiblen");
        else
           printf("Yes, I found itn");
    }
    return 0;
}