题目描述
Consider the following mathematical machine. Digits ranging from 0 to 9 are printed consecutively (clockwise) on the periphery of each wheel. The topmost digits of the wheels form a four-digit integer. For example, in the following figure the wheels form the integer 8,056. Each wheel has two buttons associated with it. Pressing the button marked with a left arrow rotates the wheel one digit in the clockwise direction and pressing the one marked with the right arrow rotates it by one digit in the opposite direction.
We start with an initial configuration of the wheels, with the topmost digits forming the integer S1S2S3S4. You will be given a set of n forbidden configurations Fi1Fi2Fi3Fi4 ( 1<=i<=n) and a target configuration T1T2T3T4. Your job is to write a program to calculate the minimum number of button presses required to transform the initial configuration to the target configuration without passing through a forbidden one.
输入
The first line of the input contains an integer N giving the number of test cases. A blank line then follows.
The first line of each test case contains the initial configuration of the wheels, specified by four digits. Two consecutive digits are separated by a space. The next line contains the target configuration. The third line contains an integer n giving the number of forbidden configurations. Each of the following n lines contains a forbidden configuration. There is a blank line between two consecutive input sets.
输出
For each test case in the input print a line containing the minimum number of button presses required. If the target configuration is not reachable print “-1''
样例输入
2
8 0 5 6
6 5 0 8
5
8 0 5 7
8 0 4 7
5 5 0 8
7 5 0 8
6 4 0 8
0 0 0 0
5 3 1 7
8
0 0 0 1
0 0 0 9
0 0 1 0
0 0 9 0
0 1 0 0
0 9 0 0
1 0 0 0
9 0 0 0
样例输出
14
-1
参考代码
暂无
解析
暂无