# UVa 11974

## Summary

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

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

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.

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

```

## Output

```Case 1: 2
Case 2: IMPOSSIBLE

```

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