1222:EXTENDED LIGHTS OUT
The aim of the game is, starting from any initial set of lights on in the display, to press buttons to get the display to a state where all lights are off. When adjacent buttons are pressed, the action of one button can undo the effect of another. For instance, in the display below, pressing buttons marked X in the left display results in the right display.Note that the buttons in row 2 column 3 and row 2 column 5 both change the state of the button in row 2 column 4,so that, in the end, its state is unchanged.
Note:
1. It does not matter what order the buttons are pressed.
2. If a button is pressed a second time, it exactly cancels the effect of the first press, so no button ever need be pressed more than once.
3. As illustrated in the second diagram, all the lights in the first row may be turned off, by pressing the corresponding buttons in the second row. By repeating this process in each row, all the lights in the first
four rows may be turned out. Similarly, by pressing buttons in columns 2, 3 ?, all lights in the first 5 columns may be turned off.
Write a program to solve the puzzle.
2 0 1 1 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 1 0 0
PUZZLE #1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 PUZZLE #2 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1
在矩阵角上的按钮改变3盏灯的状态
在矩阵边上的按钮改变4盏灯的状态
其他的按钮改变5盏灯的状态
对矩阵中的每盏灯设置一个初始状态。请你按按钮,直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时,一个操作会抵消另一次操作的结果。在下图中,第2行第3、5列的按钮都被按下,因此第2行、第4列的灯的状态就不改变
第2次按下同一个按钮时,将抵消第1次按下时所产生的结果。因此,每个按钮最多只需要按下一次。
各个按钮被按下的顺序对最终的结果没有影响
对第1行中每盏点亮的灯,按下第2行对应的按钮,就可以熄灭第1行的全部灯。如此重复下去,可以熄灭第1、2、3、4行的全部灯。同样,按下第2、3、4、5、6列的按钮,可以熄灭前5列的灯。
此时要熄灭第1行某个亮着的灯(假设位于第i列),那么唯一的办法就是按下第2行第i列的开关(因为第一行的开关已经用过了,而第3行及其后的开关不会影响到第1行)。
第2行的开关起作用后,为了熄灭第二行的灯,第3行的合理开关状态就也是唯一的,以此类推,最后一行的开关状态也是唯一的。
因此,只需枚举第一行的状态,状态数是2的6次方= 64
a[i][j]=1:灯(i, j)初始时是被点亮的
a[i][j]=0:灯(i, j)初始时是熄灭的
用一个矩阵b[5][6]表示要计算的结果
b[i][j]=1:需要按下按钮(i, j)
b[i][j]=0:不需要按下按钮(i, j)
有下列等式成立(0<i<5, 0<j<6)
a[i][j]=(b[i][j-1]+b[i][j]+b[i][j+1]+ b[i-1][j]+b[i+1][j]) % 2
b[5][6]共有2的30次方种可能取值
在每种取值情况下,看看是否找到答案;若找到,则返回;若没有,则尝试下一种取值的情况
问题1:如何进行枚举?如果每行开关数目是N那怎么办?
第二个函数deal():对b的第一行的给定取值,根据熄灯规则计算出b的其他行的值,判断这个b能否使得矩阵第五行的所有灯也恰好熄灭。
第0行、第0列和第7列不属于b矩阵范围,可全置0
b[r+1][c]=(a[r][c]+b[r][c-1]+b[r][c]+b[r][c+1] + b[r-1][c])% 2
0<r<5, 0<c<7
#include<cstdio> using namespace std ; int a[6][8] ;//表示灯的初始状态 int b[6][8] ;//表示要计算的结果 /** 对a的第一行的给定取值, 根据熄灯规则计算出a的其他行的值, 判断这个a能否使得矩阵第五行的所有灯也恰好熄灭。 */ bool deal() { int c,r ; for(r=1;r<5;r++) for(c=1;c<7;c++) b[r+1][c]=(a[r][c]+b[r][c]+b[r][c-1]+b[r][c+1]+b[r-1][c])%2 ; for(c=1;c<7;c++) if((b[5][c-1]+b[5][c]+b[5][c+1]+b[4][c])%2!=a[5][c]) return false ; return true ; } void temp() { int c ; for(c=1;c<7;c++) b[1][c] = 0 ; while(deal()==false){ b[1][1]++; c=1 ; while(b[1][c]>1){ b[1][c] = 0 ; c++ ; b[1][c]++ ; } } return ; } int main() { int cases,i,r,c ; scanf("%d",&cases) ; for(r=0;r<6;r++) b[r][0] = b[r][7] = 0;//把第0列和第7列全部置0 for(c=1;c<7;c++) b[0][c] = 0 ; for(i=0;i<cases;i++){ for(r=1;r<6;r++)//行 for(c=1;c<7;c++)//列 scanf("%d",&a[r][c]); temp(); printf("PUZZLE #%d\n", i+1); for(r=1;r<6;r++){ for(c=1;c<7;c++) printf("%d ",b[r][c]); printf("\n"); } } return 0 ; }
相关推荐
易语言枚举窗口,转载他人的 源码易语言枚举窗口,转载他人的 源码易语言枚举窗口,转载他人的 源码易语言枚举窗口,转载他人的 源码易语言枚举窗口,转载他人的 源码易语言枚举窗口,转载他人的 源码易语言枚举窗口,转载...
java 通过反射获取枚举类,及枚举类的值,枚举类枚举实例名。本项目为普通java项目
mfc 枚举进程 mfc 枚举进程 mfc 枚举进程 mfc 枚举进程 mfc 枚举进程
java枚举结果类、根据状态值获取枚举值 Controller: /** 模块类型枚举 */ model.addAttribute("mType", ModuleTypeEnum.ModuleTypeShow()); ftl: value="${mType.key}:${mType.value}” </#list>
枚举参数与对象类型进行比较,判断是否属于同一类型
从驱动开发网看到一篇《USB枚举详细过程分析》,依据自己的理解和经验对原文稍加改动。本文仅供参考,一些顺序并不是固定的。 本文描述的是Windows系统的USB枚举过程,但对嵌入式系统自行开发的USB主机驱动程序也...
枚举.pdf枚举.pdf枚举.pdf枚举.pdf枚举.pdf枚举.pdf枚举.pdf枚举.pdf枚举.pdf枚举.pdf
Java1.5提供了关键字enum,能够通过该关键字方便得定义自己须要的枚举类型,比方 enum Season { SPRING, SUMMER, AUTUMN, WINTER } 定义了一个季节枚举类型。 在本例中,对于Season.SPRING这个...
java枚举小例子,简单了解枚举的用法,适合初学者使用。
thinkPHP调用枚举类型,里面根据参数不同返回值不同,初步只封装了input(radio、check)、td、select等。
枚举算法枚举算法枚举算法.ppt
星期的枚举 告诉你关于枚举的一些简单的问题
演示如何操作Delphi 的枚举类型。 1. 包含源代码; 2. 包含执行程序 3. 演示如下函数如何使用:GetEnumName、GetEnumProp、GetEnumValue、SetEnumProp 4. 非常简单,一看就会。
代码 基于0-1整数规划隐枚举法离散型优化问题代码代码 基于0-1整数规划隐枚举法离散型优化问题代码代码 基于0-1整数规划隐枚举法离散型优化问题代码代码 基于0-1整数规划隐枚举法离散型优化问题代码代码 基于0-1整数...
易语言文件枚举实例源码,文件枚举实例,枚举文件1,枚举文件2,取值,枚举文件3,枚举文件4,取变量数据地址_文本型,API枚举线程,Push,PopN,Pop0,Count,SendMessage_Str,FindFirstFileA,FindClose,FindNextFileA,...
易语言模拟枚举类型源码,模拟枚举类型,初始化枚举类型
USB详细枚举过程(经测试正确USB详细枚举过程(经测试正确USB详细枚举过程(经测试正确USB详细枚举过程(经测试正确USB详细枚举过程(经测试正确USB详细枚举过程(经测试正确USB详细枚举过程(经测试正确USB详细枚举...
usb端口枚举,枚举所有usb端口,包括usb hub的usb端口
枚举窗口 枚举窗口 枚举窗口 枚举窗口 枚举窗口