11974 - Switch The Lights

Simple BFS problem

If we consider the states of the lamps as vertices and the set of lamps that a switch toggles as edges then we will have a graph. Run BFS on the graph for reachability to the state where the lamps are all off and for the shortest path (the fewest number of switches) to that state.

On/off state of all the lamps and the transition (the set of lamps that a switch toggles) can be represented as a N-bit binary number. This way, the state transition can be done in one simple xor operation.

Example:

Input:

3 2
1 0 1
1 1 0

So you got source node = 2^3-1=7, destination node=0

Switch 1: 1 0 1 = 1*2^0 + 0*2^1 + 1*2^2 = 5

Switch 2: 1 1 0 = 1*2^0 + 1*2^1 + 0*2^2 = 3

So, In 0 state you got: 7

In 1 state you got 2 node: (7 XOR 5) , (7 XOR 3)   --> adjacency of 7

For each node you can got M adjacency node