Computer scientists are jolly good people that enjoy a bit of fun. The latest craze is a game that consists of four wheels, each labeled (clockwise) with all the digits from zero to nine. The topmost digits of the four wheels form an integer between 0 and 9999. Each wheel has two buttons, one each to rotate it one digit to the left or to the right. Starting with an initial configuration, the aim of the game is to get to a final configuration without passing through a number of forbidden configurations in the process.
More formally, we start with an initial configuration of the wheels, with the topmost digits forming the integer \(S_1S_2S_3S_4\). You will be given a set of \(n\) forbidden configurations \(F_{i_1}F_{i_2}F_{i_3}F_{i_4}\) (\(1 \leq i \leq n\)) and a target configuration \(T_1T_2T_3T_4\). 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
This is challenge 10067 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.
Please log in to submit your solution.
Difficulty 

Average test runtime  1.17 
Points (changes over time)  10 
Tried by  10 users 
Solved by  8 users 
#  Name  Runtime  Points worth 

1  Marvin  0.24  18 
2  Bjoern  0.27  16 
3  JB  0.30  15 
4  贝尔恩德  0.38  11 
5  ,s/java/NaN/gi  0.41  11 
6  Dark  0.83  5 
7  Mac  1.50  3 
8  Skøgland  5.39  1 