EXTENDED LIGHTS OUT

From Progteam

Revision as of 03:42, 10 November 2007 by Jjx203 (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by Jjx203.


EXTENDED LIGHTS OUT
Problem Number 1222
Sorter: Uncategorized
Source: Unknown
Link: 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 Scanner reader;
	public static void main(String[] args){
		reader=new Scanner(System.in);
		int count=reader.nextInt();
		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++){
				lights[i][j]=reader.nextInt();
				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();
		}
	}
}
Personal tools