P1242 New Tower of Hanoi

There are $n$ hollow circular disks of distinct sizes, labeled from $1$ to $n$ in ascending order by size. These $n$ disks are arbitrarily nested on three pegs labeled $A$, $B$, $C$. This configuration is called the initial state. Your task is to find a shortest sequence of moves that transforms the initial state into the target state. The move rules are as follows: - Only one disk may be moved at a time. - A larger disk may not be placed on top of a smaller disk.

The first line contains an integer $n$, the total number of disks present in the states. The next three lines each contain several integers, describing the disks on pegs $A$, $B$, $C$ in the initial state, listed from bottom to top. If a line contains only the single number $0$, that peg has no disk. The following three lines each contain several integers, describing the disks on pegs $A$, $B$, $C$ in the target state, listed from bottom to top. If a line contains only the single number $0$, that peg has no disk.

Several lines, each containing a string in the format `move I from P to Q`, representing a single move. Then output one line with one integer, the minimum number of moves from the initial state to the target state.

Constraints: For $100\%$ of the testdata, $1 \le n \le 45$, and $1 \le$ each disk's index $\le n$. Each line’s disk description is listed from bottom to top. Translated by ChatGPT 5