POJ3734【状压枚举】

题意：

给你两个01矩阵，去掉矩阵B的某些行和某些列，问处理后的矩阵B能否变成矩阵A；

思路：

数据较小，状压枚举B矩阵列的数量=A矩阵列的数量时的状态，然后搞定了列，贪心判断B矩阵的行就好了；

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

#include <map>

using namespace std;

#define LL long long

#define INF 0x3f3f3f3f

char a[25][25];

char b[25][25];

bool vis[25];

map<int,int>mp;

int flag;

int n,m,nn,mm;

bool check(int tmp)

{

    int hn=0;

    int ln;

    for(int i=0;i<nn;i++)

    {

        ln=0;

        for(int j=0;j<mm;j++)

        {

            if((tmp&(1<<j))==0) continue;

            if(a[hn][ln]==b[i][j])

                ln++;

            else

                break;

        }

        if(ln==m)

            hn++;

        if(hn==n)

            return 1;

    }

    return 0;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=0;i<n;i++)

        scanf("%s",a[i]);

    scanf("%d%d",&nn,&mm);

    for(int i=0;i<nn;i++)

        scanf("%s",b[i]);

    int build=1<<mm;

    flag=0;

    for(int i=0;i<=build;i++)

    {

        int num=0;

        for(int j=0;j<mm;j++)

            if(i&(1<<j))

                num++;

        if(num==m)

        {

            if(check(i))

            {

                puts("Yes");

                return 0;

            }

        }

    }

    puts("No");

    return 0;

}