题目描述
有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
参考代码
#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");
}
解析
暂无