Problem H
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 77 Accepted Submission(s) : 27
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
爱情产生动力，灯泡照亮前程。
爱情公寓是一个情侣们都向往的地方，导致现在整幢公寓都已经住满了人。公寓一共有n(3<=n<=100)层，每层有m(3<=m<=6)个房间，从外面看上去就是一个n*m的网格。每当傍晚降临，家家户户都要开灯，用灯泡照亮他们美好的未来。可惜的是灯泡也有傲娇的时候，尤其是看到这么多情侣，所以只有一部分的房间的灯被打开了，还有一部分的灯无论房间的开关怎么动都是暗的。这个时候，身为ACMer的你勇敢的hack进了公寓的电路系统，发现这里有另外一套开关，它的规则是这样：当你改变[i,j]号灯的状态时，[i,j]上下左右的四个灯（如果有的话）也随之改变状态。改变状态的意思是从开到关，或者从关到开。聪明的你能不能通过一系列的操作使得整幢公寓的灯泡都亮起来呢？
爱情公寓是一个情侣们都向往的地方，导致现在整幢公寓都已经住满了人。公寓一共有n(3<=n<=100)层，每层有m(3<=m<=6)个房间，从外面看上去就是一个n*m的网格。每当傍晚降临，家家户户都要开灯，用灯泡照亮他们美好的未来。可惜的是灯泡也有傲娇的时候，尤其是看到这么多情侣，所以只有一部分的房间的灯被打开了，还有一部分的灯无论房间的开关怎么动都是暗的。这个时候，身为ACMer的你勇敢的hack进了公寓的电路系统，发现这里有另外一套开关，它的规则是这样：当你改变[i,j]号灯的状态时，[i,j]上下左右的四个灯（如果有的话）也随之改变状态。改变状态的意思是从开到关，或者从关到开。聪明的你能不能通过一系列的操作使得整幢公寓的灯泡都亮起来呢？
Input
输入的第一行有一个数T，表示接下来有T组测试数据。
对于每组测试数据，第一行有两个数n和m，描述见上。接下来有n行，每行有m个数，为0或1，0表示灯暗，1表示灯亮。
对于每组测试数据，第一行有两个数n和m，描述见上。接下来有n行，每行有m个数，为0或1，0表示灯暗，1表示灯亮。
Output
对于每组测试数据，输出一行，如果能通过一些列操作使所有的灯都亮起来那么输出“YES”（不含引号），否则输出“NO”（不含引号）。
Sample Input
2
3 3
0 0 0
0 1 0
0 0 0
3 3
0 0 0
0 0 0
0 0 0
Sample Output
YES
YES
类似
http://blog.csdn.net/zy691357966/article/details/40082595
代码如下：
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
using namespace std;
void init()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
int n,m;
int MAP[105][10];
int A[105][10];
int fx[5]={0,0,0,1,-1},fy[5]={0,1,-1,0,0};
void COPY()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
A[i][j]=MAP[i][j];
}
}
void CHANGE(int i,int j)
{
A[i][j]=A[i][j]^1;
for(int k=1;k<=4;k++)
{
A[i+fx[k]][j+fy[k]]^=1;
}
}
void input()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&MAP[i][j]);
}
}
int dfs(int line)
{
if(line==n+1) {
int OK=1;
for(int i=1;i<=m;i++)
if(A[line-1][i]==0) OK=0;
if(OK) return 1;
else return 0;
}
for(int i=1;i<=m;i++)
{
if(A[line-1][i]==0) CHANGE(line,i);
}
return dfs(line+1);
}
void solve()
{
int OK=0;
for(int i=0;i<=(1<<m)-1;i++)
{
COPY();
for(int j=1;j<=m;j++)
{
int temp=(i>>(j-1))&1;
if(temp==1)
{
CHANGE(1,j);
}
}
if(dfs(2))
{
OK=1;
break;
}
}
if(OK) printf("YES\n");
else printf("NO\n");
}
int main()
{
//init();
int T;
cin>>T;
while(T--)
{
input();
solve();
}
}