开关和灯
时间: 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;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。