Three basic transformations, identified by the letters `A', `B' and `C', can be applied to a sheet:
- 'A': exchange the top and bottom row,
- 'B': single right circular shifting of the rectangle,
- 'C': single clockwise rotation of the middle four squares.
You are to write a program that computes a minimal sequence of basic transformations that transforms the initial configuration above to a specific target configuration.
PROGRAM NAME: msquare
INPUT FORMATA single line with eight space-separated integers (a permutation of (1..8)) that are the target configuration.
SAMPLE INPUT (file msquare.in)
2 6 8 4 5 7 3 1
|Line 1:||A single integer that is the length of the shortest transformation sequence.|
|Line 2:||The lexically earliest string of transformations expressed as a string of characters, 60 per line except possibly the last line.|
SAMPLE OUTPUT (file msquare.out)
Solution:This is a shortest path problem. Use BFS + Hash Table to go through every state.
The only problem here is if I use array to store and identify the state, that would exceed time limit. Since we only have 8 digits, we could represent it as an INT.
I think this problem could be solved with DFS using recursion and hash table.