In this problem we consider a modification of the classical Hanoi Towers game. The rules of our modification are as follows:
- There are three pegs: peg A, peg B and peg C.
- Each peg initially contains zero or more discs.
- All discs have the same size and there are three types of discs: type A, type B and type C.
- In one move you can move a disc from the top of one peg onto the top of another peg.
- Your goal is to have all discs of type A on peg A, all discs of type B on peg B and all discs of type C on peg C.
- You must achieve your goal in the minimum possible number of moves.
The initial locations of the discs are given in the Strings **pegA**, **pegB** and **pegC**. Each character of **pegA** represents a disc located on peg A, where 'A' represents a disc of type A, 'B' represents a disc of type B and 'C' represents a disc of type C. The discs are given in order, from bottom to top. **pegB** and **pegC** describe the discs on pegs B and C, respectively, in the same format.
Return the minimum number of moves required to achieve the goal of the game. |