Can anybody help me on this?
There are 8 statues 0,1,2,3,4,5,6,7 . Each statue is pointing in one of the following four direction North, South, East or West. John would like to arrange the statues so that they all point in same direction. However John is restricted to the following 8 moves which correspond to rotation each statue listed 90 degrees clockwise. (N to E, E to S, S to W, W to N)
Move A: 0,1 B: 0,1,2 C: 1,4,5,6 D: 2,5 E: 3,5 F: 3,7 G: 5,7 H: 6,7
Help John figure out fewest number of moves to help point all statues in one direction.
Input : A string initialpos consisting of 8 chars. Each char is either 'N,'S,'E,'W'
Output: An integer which represents fewest no. of moves needed to arrange statues in same direction. If no sequence possible then return -1.
Sample test cases: input: SSSSSSSS Output: 0 Explanation: All statues point in same direction. So it takes 0 moves
Test case 1: Input : WWNNNNNN Output: 1 Exp: John can use Move A which will make all statues point to North
Test Case 3: input: NNSEWSWN Output: 6 Exp: John uses Move A twice, B once, F twice, G once. This will result in all statues facing W.
There was a similar problem on USACO (1.4.2 Clocks), it is solvable with BFS.
A key observation to make is that rotating a statue 4 times is same like not rotating it at all, so you can use each move a maximum of 3 times.
You have 8 possible moves, each of them used between 0 and 3 times, giving you 4^8 = 65536 total combinations. Feel free to try them all if you want.
just use BFS. keep the position of each statue in the state. there will be 4^8 states.