EXTENDED LIGHTS OUT

 This problem has been solved by Jjx203.

 Sorter: Uncategorized Unknown http://acm.pku.edu.cn/JudgeOnline/problem?id=1222

Idea: The original lights are 5*6 matrix. I use a brute force on the first colomn, i.e I try all possible combinations of key presses on the first colomn and see which way yields the right solution. To do this, I use a counter m that counts from 0 to 31, each corresponding to a binary number. So if m=6, it corresponds to press the button 0 1 1 0 0, i.e.

```0 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
```

Then I know which lights in the first colomn are on. I press a buttons on the second colomn if the light to the left of this button is on, don't press it otherwise. Then I get what lights to press on the second colomn. Then I decide on what buttons to press on the third... Until I finished pressing the buttons on the last colomn(colomn 6). Then I check if the 6th colomn has any light on. If it doesn't, then this is the solution. If it does, then discard this solution and increment the counter m by 1 and try the next combination. As the input is guaranteed to have solution, so there will always be one point that a solution is discovered.

```import java.util.*;

public class Main{
public static int[][] lights;
public static int[][] presses;
public static int[][] temp;
public static void main(String[] args){
for(int i=1;i<=count;i++){
createLights();
for(int m=0;m<32;m++){
randomPressOnColomnOne(m);
pressAllExceptColomnOne();
if(lastColomnIsGood()){
System.out.println("PUZZLE #"+i);
printP();
presses=new int[5][6];
break;
}
presses=new int[5][6];
restoreLights();
}
}
}

public static void createLights(){
lights=new int[5][6];
presses=new int[5][6];
temp=new int[5][6];
for(int i=0;i<5;i++){
for(int j=0;j<6;j++){
temp[i][j]=lights[i][j];
}
}
}

public static void restoreLights(){
for(int i=0;i<5;i++){
for(int j=0;j<6;j++){
lights[i][j]=temp[i][j];
}
}
}

public static void randomPressOnColomnOne(int x){
int remain=x;
if(remain/16==1){
press(4,0);
remain=remain%16;
}
if(remain/8==1){
press(3,0);
remain=remain%8;
}
if(remain/4==1){
press(2,0);
remain=remain%4;
}
if(remain/2==1){
press(1,0);
remain=remain%2;
}
if(remain==1){
press(0,0);
}
}

public static void pressAllExceptColomnOne(){
for(int j=1;j<6;j++){
for(int i=0;i<5;i++){
if(lights[i][j-1]==1){
press(i,j);
}
}
}
}

public static boolean lastColomnIsGood(){
for(int i=0;i<5;i++){
if(lights[i][5]==1){
return false;
}
}
return true;
}

public static void press(int i,int j){
presses[i][j]=1;
lights[i][j]=(lights[i][j]+1)%2;
if(i!=0){
lights[i-1][j]=(lights[i-1][j]+1)%2;
}
if(i!=4){
lights[i+1][j]=(lights[i+1][j]+1)%2;
}
if(j!=0){
lights[i][j-1]=(lights[i][j-1]+1)%2;
}
if(j!=5){
lights[i][j+1]=(lights[i][j+1]+1)%2;
}
}

public static void printL(){
System.out.println("Lights:");
for(int i=0;i<5;i++){
for(int j=0;j<6;j++){
System.out.print(lights[i][j]+" ");
}
System.out.println();
}
}

public static void printP(){
//System.out.println("Presses:");
for(int i=0;i<5;i++){
for(int j=0;j<6;j++){
System.out.print(presses[i][j]+" ");
}
System.out.println();
}
}
}
```