easyfinding（codevs 3280）

3280 easyfinding

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 Description

给一个M 行N 列的01 矩阵，让你选出一些行（不一定选出全部行）使得每一列都有
且只有一个1。其中M<= 16，N<=300 。

输入描述 Input Description

输入含有多组数据。以文件结束符（eof ）为结束。最多会有500 组。
输入之间会有梯度，也就是不是每组输入都是500 组。
对每组数据，第一行：两个由空格隔开的整数M 和N 。然后是M 行每行N 个等于0
或者等于1 的整数，整数之间由空格隔开。

输出描述 Output Description

对每组数据输出一行，如果可以达到题中要求，输出Yes 否则输出No 。均不包括引号。

样例输入 Sample Input

3 3
0 1 0
0 0 1
1 0 0
4 4
0 0 0 1
1 0 0 0
1 1 0 1
0 1 0 0

样例输出 Sample Output

Yes
No

（codevs有一个数据让我陷入死循环了，所以在程序中略有改动）

#include<cstdio>

#include<iostream>

#include<vector>

#include<cstring>

#define M 310

using namespace std;

int map[M][M],n,m,head,tail;

int v[M][M],q[M],flag;

struct node

{

    int vis[M];

};node a[M];

int ok(int x)

{

    for(int i=;i<=m;i++)

      if(!a[x].vis[i])return ;

    return ;

}

void init()

{

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

    {

        for(int j=;j<=m;j++)

        {

            scanf("%d",&map[i][j]);

            if(map[i][j])v[i][++v[i][]]=j;

        }

    }

    while(head<=tail)

    {

        if(tail>*n)return;//防止死循环（其实就是作弊 >_<~~~)

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

        {

            q[++tail]=i;

            for(int j=;j<=m;j++)

              a[tail].vis[j]=a[head].vis[j];

            int ff=;

            for(int j=;j<=v[i][];j++)

              if(a[tail].vis[v[i][j]])

                ff=;

            if(!ff)

            {

                for(int j=;j<=v[i][];j++)

                  a[tail].vis[v[i][j]]=;

                if(ok(tail))

                {

                    printf("Yes\n");

                    flag=;

                    return;

                }

            }

            else tail--;

        }

        head++;

    }

}

int main()

{

    while(scanf("%d%d",&n,&m)==)

    {

        memset(a,,sizeof(a));

        memset(v,,sizeof(v));

        memset(q,,sizeof(q));

        head=;tail=;flag=;

        init();

        if(!flag)printf("No\n");

    }

    return ;

}

巴特西

easyfinding（codevs 3280）

3280 easyfinding

最新文章

热门文章