加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

POJ PKU 3600 模拟

(2010-04-12 23:21:50)
标签:

poj

pku

3600

it

分类: 杂题

题目描述:

给你两个0, 1矩阵,前小后大,问你能不能把后面大的矩阵的一些行或者一些列删除后得到和那个小的一样的矩阵。

解题报告:

设小的行列为r,c, 大的是R,C。

则要删除的列为C - c,

枚举从C里面选C-c列的组合,最多也不过180000。

对于每个枚举,扫描行,看看能不能找出一些行和小的匹配。

每个扫描耗时(r R) * C。

#include<iostream>
using namespace std;
int r, c, n, m, x[20][20], y[20][20], vst[20], flag;
void input(int z[20][20], int a, int b)
{
    getchar();
    for(int i = 0; i < a; i )
    {
        for(int j = 0; j < b; j )
            z[i][j] = getchar() - '0';
        getchar();
    }
}
void jeogia(int deep, int from)
{
    if (deep == 0)
    {
        int i = 0, j = 0, l, k;
        while(i < r && j < n)
        {
            k = l = 0;
            for(; k < c; k )
            {
                while(vst[l] && l < m) l ;
                if (l >= m || y[j][l] != x[i][k])
                    break;
                l ;
            }
            if (k == c) i , j ;
            else j ;
        }
        if (i == r)
            flag = true;
        return;
    }
    for(int i = from; i < m && flag == 0; i )
    {
        vst[i] = 1;
        jeogia(deep - 1, i 1);
        vst[i] = 0;
    }
}
int main()
{
    scanf("%d%d", &r, &c);
    input(x, r, c);
    scanf("%d%d", &n, &m);
    input(y, n, m);
    memset(vst, 0 ,sizeof(vst)), flag = false;
    jeogia(m - c, 0);
    if (flag)
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有