Chenglei Si
Sep 7, 2018 · 2 min read

POJ 1222 Lights Off (Enumeration)

This question asks for a strategy to press the lights so that all lights are off. Every time you press a light, the 4 lights (2 or 3 for corner or edge) next to it as well as itself will be switched on or off. Two switches cancel each other out.

We can solve it by enumeration. Once we have settled the first row of lights, for those lights that are still on in the first row, we must press the light below them, otherwise, there is no other way to switch them off. Hence the pressing of the second row is actually determined by the first row. Similarly, we can settle the pressing for all the following rows. We need to check after the last row has been settled, whether all lights in the last row are off as well.

This is a typical example of which we enumerate over a few states (in this case the first row of lights), and once a state is chosen, all the rest variables are all settled.

There are some useful tricks. First, we pad one more row on top and one more column on both sides with all zeros. This enables us to handle the corner and edge cases just like all other cases. Second, instead of a terrible nested for loop, we can use simulated binary addition to do the enumeration. Since the pressing of the first row is represented by 6 binary digits, we can treat it as a binary number. Every time we increase the number by 1 and it will represent a new state.

Another detail to take note of is that you can also choose to enumerate over the first column instead of the first row. You can save more time with this method if the number of rows if smaller than the number of columns (because you have fewer states to enumerate). The algorithm is essentially the same for both ways.

Accepted solution:

#include <iostream>
#include <cstring>
using namespace std;

const int row = 5, col = 6;
int puzzle[row+1][col+2], press[row+1][col+2];

bool check(){
//first infer all presses
for(int r=2; r<=row; r++){
for(int c=1; c<=col; c++){
press[r][c] = (puzzle[r-1][c] + press[r-1][c-1] + press[r-1][c]
+ press[r-1][c+1] + press[r-2][c])%2;
}
}

//then check the last row
for(int c=1; c<=col; c++){
if((puzzle[row][c] + press[row][c] + press[row][c-1] + press[row][c+1]
+ press[row-1][c])%2 == 1)
return false;
}

return true;
}

void output(){
for(int r=1; r<=row; r++){
for(int c=1; c<=col; c++){
cout<<press[r][c]<<' ';
}
cout<<endl;
}
}

void enumerate(){
int c;
while(check()==false){
c = 1;
press[1][c]++;
//simulate binary adding
while(press[1][c]>1){
press[1][c]=0;
c++;
press[1][c]++;
}
}
output();
}

int main(){
int cases;
cin>>cases;
for(int ca=0; ca<cases; ca++){
memset(puzzle, 0, sizeof(puzzle));
memset(press, 0, sizeof(press));
for(int r=1; r<=row; r++){
for(int c=1; c<=col; c++){
cin>>puzzle[r][c];
}
}

cout<<"PUZZLE #"<<ca+1<<endl;
enumerate();
}
}

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade