1222(部分枚举)

1222:EXTENDED LIGHTS OUT

总时间限制:

1000ms

内存限制:

65536kB

描述

In an extended version of the game Lights Out, is a puzzle with 5 rows of 6 buttons each (the actual puzzle has 5 rows of 5 buttons each). Each button has a light. When a button is pressed, that button and each of its (up to four) neighbors above, below, right and left, has the state of its light reversed. (If on, the light is turned off; if off, the light is turned on.) Buttons in the corners change the state of 3 buttons; buttons on an edge change the state of 4 buttons and other buttons change the state of 5. For example, if the buttons marked X on the left below were to be pressed,the display would change to the image on the right.

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.

输入

The first line of the input is a positive integer n which is the number of puzzles that follow. Each puzzle will be five lines, each of which has six 0抯 or 1抯 separated by one or more spaces. A 0 indicates that the light is off, while a 1 indicates that the light is on initially.

输出

For each puzzle, the output consists of a line with the string: "PUZZLE #m", where m is the index of the puzzle in the input file. Following that line, is a puzzle-like display (in the same format as the input) . In this case, 1's indicate buttons that must be pressed to solve the puzzle, while 0抯 indicate buttons, which are not pressed. There should be exactly one space between each 0 or 1 in the output puzzle-like display.

样例输入

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

翻译：

 1.问题描述：有一个由按钮组成的矩阵，其中每行有6个按钮，共5行。每个按钮的位置上有一盏灯。当按下一个按钮后，该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即，如果灯原来是点亮的，就会被熄灭；如果灯原来是熄灭的，则会被点亮。
在矩阵角上的按钮改变3盏灯的状态
在矩阵边上的按钮改变4盏灯的状态
其他的按钮改变5盏灯的状态

 

2.在上图中，左边矩阵中用X标记的按钮表示被按下，右边的矩阵表示灯状态的改变
对矩阵中的每盏灯设置一个初始状态。请你按按钮，直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果。在下图中，第2行第3、5列的按钮都被按下，因此第2行、第4列的灯的状态就不改变

3.请你写一个程序，确定需要按下哪些按钮，恰好使得所有的灯都熄灭。根据上面的规则，我们知道
第2次按下同一个按钮时，将抵消第1次按下时所产生的结果。因此，每个按钮最多只需要按下一次。
各个按钮被按下的顺序对最终的结果没有影响
对第1行中每盏点亮的灯，按下第2行对应的按钮，就可以熄灭第1行的全部灯。如此重复下去，可以熄灭第1、2、3、4行的全部灯。同样，按下第2、3、4、5、6列的按钮，可以熄灭前5列的灯。

 

解题思路：

 

1.经过观察，发现第1行就是这样的一个“局部”。因为第1行的各开关状态确定的情况下，这些开关作用过后，将导致第1行某些灯是亮的，某些灯是灭的。
此时要熄灭第1行某个亮着的灯（假设位于第i列），那么唯一的办法就是按下第2行第i列的开关（因为第一行的开关已经用过了，而第3行及其后的开关不会影响到第1行)。

 

2.为了使第1行的灯全部熄灭，第2行的合理开关状态就是唯一的。
第2行的开关起作用后，为了熄灭第二行的灯，第3行的合理开关状态就也是唯一的，以此类推，最后一行的开关状态也是唯一的。

 

3.总之，只要第1行的状态定下来，比如叫A，那么剩余行的情况就是确定唯一的了。推算出最后一行的开关状态，然后看看最后一行的开关起作用后，最后一行的所有灯是否都熄灭，如果是，那么A就是一个解的状态。如果不是，那么A不是解的状态，第1行换个状态重新试试。
因此，只需枚举第一行的状态，状态数是2的6次方= 64

 

具体实现：

1.

用一个矩阵a[5][6]表示灯的初始状态
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次方种可能取值

 

2.建立2个函数

第一个函数temp()，对b的第一行元素的每种取值进行枚举
在每种取值情况下，看看是否找到答案；若找到，则返回；若没有，则尝试下一种取值的情况
问题1：如何进行枚举？如果每行开关数目是N那怎么办?
第二个函数deal()：对b的第一行的给定取值，根据熄灯规则计算出b的其他行的值，判断这个b能否使得矩阵第五行的所有灯也恰好熄灭。

3.计算出b的其他行的值

用一个68的数组来表示按钮矩阵：简化计算数组下一行的值的计算公式
第0行、第0列和第7列不属于b矩阵范围，可全置0

给定b的第一行取值，计算出b的其他行的值
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

 

 

解决代码：G++

 

#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 ;
}