开关和灯

开关和灯

时间： 1ms        内存：128M

描述：

有n个开关和m盏灯，对于一盏灯，只要存在一个控制这个灯的开关是开着的，这个灯就会被点亮。然后给你n×m的01矩阵，如果i行j列为1代表开关i可以控制灯j，问你能否删掉一个开关，使得所有的灯仍旧能被点亮。

输入：

n,m(1<=n,m<=2000)n行m列的01矩阵。(输入的每一行均为一个数字，也可按字符串输入)

输出：

如果可以找到可行解，请输出”YES”,否则，输出“NO”。

示例输入：

4 5
10101
01000
00111
10000

示例输出：

YES

提示：

参考答案（内存最优[1120]）：

#include<stdio.h>
int main()
{
    int a,b,c,d,e,f,g,h,i,o;
    f=1;i=0;o=0;
    scanf("%d %d",&a,&b);
    int n[b],m[a],p[b];
    for(c=1;c<=a;c++)
        scanf("%d",&m[c]);
    for(c=1;c<=b;c++)
    {
        n[c]=0;
    }
    for(c=1;c<=a;c++)
    {
        h=m[c];f=1;
        for(d=1;d<=b;d++)
        {
                       f=10*f;
                            g=h%f;
                            h=h-g;
                            if(g!=0)
                                n[d]=n[d]+1;
        }}
                for(d=1;d<=b;d++)
p[d]=n[d];
        for(c=1;c<=a;c++)
        {
            h=m[c];f=1;
                    for(d=1;d<=b;d++)
                    {
                        f=10*f;
                        g=h%f;
                        h=h-g;
                        if(g!=0)
                            n[d]=1;
                            else n[d]=0;
                    }
                            for(d=1;d<=b;d++)
{if(p[d]-n[d]>=1)
{
    i=i+1;
}
else
{i=0; break;}}
if(i!=0)
{printf("YES");o=1; break;}
        }
    if(o==0)
        printf("NO");

}

参考答案（时间最优[2]）：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n,m;
char ans[2005][2005];
int res[2005];
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
         for(int j=0;j<m;j++){cin>>ans[i][j];if(ans[i][j]=='1')res[j]++;}
         //getchar();
    }
    for(int i=0;i<n;i++)
    {
        int j;
        int flag=1;
        for(j=0;j<m;j++)
        {
            if(ans[i][j]=='1')
            {
                int c=res[j]-1;
                if(c<=0){flag=0; break;}
            }
        }
        if(flag){
        cout<<"YES";
        return 0;}
    }
    cout<<"NO";
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。