On the Ox coordinate axis, there are initially 3 pieces at x, y, z. At each step you can move a piece according to the rule: If there are 2 pieces in position n and m then move the piece in position n to position n' symmetrical to n through m if n' has no pieces. Find a way to move 3 pieces at x, y, z so that at the end we get 3 pieces at u, v, w.
- Input: 6 numbers x, y, z and u, v, w. (-10^6 < x,y,z,u,v,w < 10^6)
- Output: K - number of steps moved. The next K lines are the positions of the 3 pieces in each step
Example:
- Input:
3 4 5 1 2 3
Currently 3 chess pieces are at positions 3,4,5, need to move them to positions 1,2,3
- Output:
2
3 2 5
3 2 1
- Step 0: 3 4 5
- Step 1: Positions 4 and 3 both have pieces, move the piece at position 4 to 2 (because 2 is the symmetry of 4 over 3 and there are no pieces at 2) => 3, 2, 5
- Step 2: Positions 5 and 3 both have pieces, move the piece in position 5 to 1 (because 1 is the symmetry of 5 over 3 and there are no pieces at 1) => 3, 2, 1
Note:
- As long as 3 pieces are obtained in u,v,w, it is not necessary to return chess piece 1 to u, piece 2 to v, and piece 3 to return to w.
- You can move as many times as you want
My idea is to use backtracking to look at all cases. But (-10^6 <= u, v, w, a, b, c <= 10^6) so my algorithm got TLE.
Is there a better approach? Thanks everyone.