9509 开灯 9509 开灯 Description 输入格式 输出格式 输入样例 输出样例 提示 来源 作者
时间限制:1000MS 内存限制:65535K
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC
Description
有16的开关分别控制16盏灯，开关排列成4*4的矩形，这些开关有这样的关系： 你改变其中一个开关的状态，与其同行和同列的开关的状态也跟着改变。先给出一个这些开关的初始状态，要求将所有的开关都打开，让所有的灯都亮起来，要求按下开关的次数最少。
输入格式
第一行输入一个整数t，表示有多少个case，每个case之间有一空行，每个case输入一个0、1组成的4*4的矩阵，0表示开关状态为关，1表示开关状态为开。
输出格式
每个case输出一行，让所有灯都亮的最少按开关数。
输入样例
1 1011 1111 1111 1011
输出样例
6
提示
分别按下（1,1），（1,3），（1,4），（4,1），（4,3），（4,4）6个开关就行了
对于
1111
1011
1111
1111
要把第二行和第二列的灯各按一次。
来源
Zyq
作者
a470086609
如果只是为了ac掉这道题目的话可以不用任何算法，只要按它最后给的提示找规律就可以了。至于怎么找出来的，自己去想(其实我不知道怎么解释=.=)... 大致如下：在一个4*4的表中输入完数据后，从头到尾扫一遍，如果遇到'0'的话就把它同行和同列的灯都按一次；如果有哪些灯被按了2n（n为整数）次的话，其被按的次数就会被抵消掉(即被按了0次)，但如果是2n+1(n为整数)次的话，就算是被按了一次。另外，需要将被按过的灯存放在另一个表里面好在最后统计总共的按灯次数。
XJB扯了一通...感觉表达的并不清楚...可能不一定看的懂...那就索性别看解释直接看代码然后自己在纸上模拟一遍吧。。。
1 #include <stdio.h> 2 3 int main() 4 { 5 int T,i,j,t_i,t_j; 6 scanf("%d",&T); 7 getchar(); 8 while(T--) 9 { 10 11 int book[10][10];int cnt=0; 12 char a[10][10]; 13 //初始化标记数组 14 for(i=0;i<4;i++) 15 for(j=0;j<4;j++) 16 book[i][j]=0; 17 // 18 for(i=0;i<4;i++) 19 { 20 for(j=0;j<4;j++) 21 scanf("%c",&a[i][j]); 22 getchar(); 23 } 24 // 25 for(i=0;i<4;i++) 26 for(j=0;j<4;j++) 27 if(a[i][j]=='0') 28 { 29 for(t_j=0;t_j<4;t_j++) 30 { 31 if(book[i][t_j]==0) 32 book[i][t_j]=1; 33 else book[i][t_j]=0; 34 } 35 for(t_i=0;t_i<4;t_i++) 36 { 37 if(t_i==i) continue; 38 if(book[t_i][j]==0) 39 book[t_i][j]=1; 40 else book[t_i][j]=0; 41 } 42 } 43 // 44 for(i=0;i<4;i++) 45 for(j=0;j<4;j++) 46 if(book[i][j]==1) 47 cnt++; 48 printf("%d ",cnt); 49 if(T != 0) getchar(); 50 } 51 return 0; 52 }
因为这个表的灯只有4*4个，所以用了下深搜的无脑暴力枚举(2^16种情况)，虽然是多个case但用200ms也给过了....只是代码写的很丑...美化的漂亮一点后的在下面给出：
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 struct table 5 { 6 int map[4][4]; 7 int open; 8 }; 9 table a; 10 int ans; 11 //改变灯的状态 12 void change(int x,int y) 13 { 14 a.map[x][y]=!a.map[x][y]; 15 if(a.map[x][y]) 16 a.open++; 17 else 18 a.open--; 19 } 20 //深度优先搜索（简单暴力） 21 void dfs(int seat,int sum_open) //seat代表当前搜索到的灯的位置，open代表当前已经按过灯的次数 22 { 23 if(a.open==16)//16盏灯都已经亮了 24 { 25 if(ans>sum_open) 26 ans=sum_open; //取开关次数最小的 27 return; 28 } 29 else if(seat==16)//表明已经搜索到最后一盏灯了 30 { 31 return; 32 } 33 // 34 int x=seat/4,y=seat%4; 35 dfs(seat+1,sum_open);//两个分支的其中一个，就是什么都不按，直接进入下一个位置 36 for(int i=0;i<4;i++) 37 change(i,y); 38 for(int i=0;i<4;i++) 39 { 40 if(i==y) continue; 41 change(x,i); 42 } 43 dfs(seat+1,sum_open+1);//这个是两个分支的另外一个，上面两个for循环是按下当前seat位置的灯的操作，然后搜索下一个位置 44 // 45 for(int i=0;i<4;i++) 46 change(i,y); 47 for(int i=0;i<4;i++) 48 { 49 if(i==y) continue; 50 change(x,i); 51 } 52 } 53 int main() 54 { 55 int T; int i,j; 56 scanf("%d",&T); 57 while(T--) 58 { 59 a.open=0; ans=666;//ans最大值是16 60 memset(a.map,0,sizeof(a.map)); 61 for(i=0;i<4;i++) 62 { 63 char line[6]; 64 scanf("%s",line); 65 for(j=0;j<4;j++) 66 { 67 if(line[j]=='1') 68 { 69 a.map[i][j]=1; 70 a.open++; 71 } 72 } 73 } 74 // 75 dfs(0,0);//初始状态是从第0个位置开始，已经按下0个开关 76 printf("%d ",ans); 77 } 78 return 0; 79 }