魔法盒
标签： 同行同列加法 2016-12-05 08:17阅读(4)评论(0)编辑删除魔法盒
时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte总提交 : 78 测试通过 : 23
描述
这天Jed教练给大家出了一道题目，想测试一下大家近期的训练状况。题目的内容如下：给你一个n*m的01矩阵，你现在有一个神奇的魔法盒，如果把这个魔法盒放到矩阵的某一个位置，那么与魔法盒同行同列的 ”1” 都会变成 ”0” (“0”不会有变化)，现在问你能否用这个魔法盒把01矩阵里的1全部变成0 (注意：这个魔法盒只能使用一次，即你只有一次变动矩阵的机会)。
输入
本题为多组数据评测。
第一行 包含一个整数T(1≤T≤10)，代表数据组数。
对于每组测试数据：
第一行 包含两个整数 n, m(1≤n, m≤100)，分别表示矩阵的行数和列数。
接下来n行，每行是一个01字符串，描述整个01矩阵的状态。
输出
如果你能做到仅使用一次魔法盒把矩阵所有的1都变成0的话 输出“Yes”.
样例输入
2
2 3
110
101
3 3
010
111
000
样例输出
No
Yes
代码如下：
/*
_...---.._
,' ~~"--..
/ ~"-._
/ ~-.
/ . `-.
\ -.\ `-.
\ ~-. `-.
,-~~\ ~.
/ \ `.
. \ `.
| \ .
| \ \
. `. \
\ \
` `. \
` \. \
` \`. \
. \ -. \
` -. \
. ` - \ .
` \ ~- \
` . ~. \
. \ -_ \
` - \
. | ~. \
` | \ \
. | \ \
` | `. \
` ` \ \
. . `. `.
` : \ `.
\ ` \ `.
\ . `. `~~-.
\ : ` \ \
. . \ : `.\
` : \ | | .
\ . \ | |
\ : \ ` | `
. . | |_ .
` `. ` ` | ~.;
\ `. . . .
. `. ` ` `
`. `._. \ `.\
` < \ `. | .
` ` : ` | |
` \ ` | |
`. | \ : .' |
"Are you crying? " ` | \ `_-' |
"It's only the rain." : | | | : ;
"The rain already stopped."` ; |~-.| : '
"Devils never cry." : \ | ` ,
` \` : '
: \` `_/
` .\ "For we have none. Our enemy shall fall."
` ` \ "As we apprise. To claim our fate."
\ | : "Now and forever. "
\ .' : "We'll be together."
: : "In love and in hate"
| .'
| : "They will see. We'll fight until eternity. "
| ' "Come with me.We'll stand and fight together."
| / "Through our strength We'll make a better day. "
`_.' "Tomorrow we shall never surrender."
sao xin*/
#include <vector>
#include <iostream>
#include <string>
#include <map>
#include <stack>
#include <cstring>
#include <queue>
#include <list>
#include <cstdio>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <ctype.h>
#include<functional>
#define INF 0xfffffff
#define eps 1e-6
#define LL long long
using namespace std;
const int maxn=1e3+5;
const int maxx=1e4+5;
const double q = (1 + sqrt(5.0)) / 2.0; // 黄金分割数
/*
std::hex <<16进制 cin>>std::hex>>a>>std::hex>>b
cout.setf(ios::uppercase);cout<<std::hex<<c<<endl;
b=b>>1; 除以2 二进制运算
//f[i]=(i-1)*(f[i-1]+f[i-2]); 错排
/ for (int i=1; i<=N; i++)
for (int j=M; j>=1; j--)
{
if (weight[i]<=j)
{
f[j]=max(f[j],f[j-weight[i]]+value[i]);
}
}
priority_queue<int,vector<int>,greater<int> >que3;//注意“>>”会被认为错误，
priority_queue<int,vector<int>,less<int> >que4;////最大值优先
//str
//tmp
//vis
//val
//cnt 2486*/
int main()
{
int T;
cin>>T;
while(T--)
{
int sum1=0,sum2=0;
char a[105][105];
int b[105][105];
int flag=0;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i]+1;//从下标1开始输入，只用与char类型
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
b[i][j]=a[i][j]-'0';//需要一个int二维数组来存放数据
sum1+=b[i][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
sum2=sum1;
for(int k=1;k<=n;k++)
if(b[k][j]==1)//列不变，行变
{
sum2--;
// cout<<sum2<<"wx"<<endl;
}
for(int k=1;k<=m;k++)//并列关系
{
if(k==j)
continue;//同列时跳过
if(b[i][k]==1)
{
sum2--;
//cout<<sum2<<"wpx"<<endl;//行不变列变
}
}
if(sum2==0) flag=1;//标记是否完成
}
if(flag)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}