UVa 11974

From Algorithmist
Jump to navigation Jump to search

11974 - Switch The Lights[edit]

Summary[edit]

There are N lamps (N <= 15) and M switches (M <= 100). The switches can toggle some of the lamps. Find out whether it is possible to turn off all the lamps and the minimal number of switches required if possible. Initially, all the lamps are on.

Explanation[edit]

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.

Optimizations[edit]

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.

Solutions[edit]

Input[edit]

2
2 2
0 1
1 0
3 2
1 0 1
1 1 0

Output[edit]

Case 1: 2
Case 2: IMPOSSIBLE

Categories here, use the form [[Category:UVa Online Judge|11974]] [[Category: Category Name]], see Categories for a list