There are n boxes, numbered 1-n. Each box is locked, such that it can be opened by only one corresponding type of key (also numbered 1-n). These keys are randomly scattered in the boxes (one box may have any number of keys, one key may have any number of duplicates), and then all boxes are shut. A treasure (numbered 0) has also been locked in many of the boxes.
You have hired a locksmith to retrieve all the treasure. He charges for each box he cracks open. There is no charge for opening a box for which the key is already available.
Input is the contents of each box. You can decide the format of the input.
Output the minimum cost required to get the treasures.
- Your algorithm may take a long time, but that is irrelevant.
- Shortest code wins.
- No need to bother about invalid input.
Here line i represents the keys present in box i.
2 0 3 4 0 5 6 0 6 0
2 0 3 0 4 0 6 5 0
2 4 0 3 0 1 0 6 5 0
1 3 4 2 6 5