ZOJ Problem Set - 2961
A locked spinner puzzle is a puzzle where you can only change wheels in groups. It is a common puzzle to achieve some value on the spinners by only changing them in the allowed groups.
Assume a row of D numbered wheels, such as what is found on a combination lock on a briefcase.
Each wheel will be labeled sequentially with the digits 0 through 9. And there are a series of buttons with labels that are D digits long. For example, D may be 4 and the labels are 1000 1200 1002 0111 and 0100. Pressing the button labeled 1000 moves the first wheel once, but leaves the others alone, while pressing the button labeled 1002 moves the first wheel once and the fourth wheel twice, leaving the center buttons unchanged. Given the initial state and final state of the wheels, you are to provide a combination of pressing to transform from the initial state to the final state with minimum number of pressing to open the lock.
The input to your program will be several spinner puzzles. Each puzzle begins with a line containing two integers D (1 <= D <= 6) the number of wheels, and N (1 <= N <= min(100, 10^D) ) the number of buttons. The next N lines will each gives a button with D digits label. Last line contains two labels which are the initial state and the final state, respectively.
For each puzzle, print the minimum number of pressing to open the lock in the first line. Then print the labels pressed in lexicographic order, each in one line. If there are several ways to do with the minimum number of pressing, make the concatenation of the labels pressed lexicographic minimum (see hint for detail). Print "-1" in a line if can't open the lock.
3 3 100 010 001 000 111 4 3 0200 0300 0400 0400 0000 2 1 99 00 01
3 001 010 100 2 0200 0400 -1
For the second sample: pressing 0300 twice also works, but "03000300" is larger than "02000400".
Author: GAO, Yuan
Source: ZOJ Monthly, May 2008