11974 - Switch The Lights
Solution Description :
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 |
||||||||||