Encuentra una forma de mover 3 piezas a la posición objetivo mediante la simetría.
En el eje de coordenadas de Ox, hay inicialmente 3 piezas en x, y, z. En cada paso, puedes mover una pieza de acuerdo con la regla: si hay 2 piezas en las posiciones n y m, entonces mueve la pieza en la posición n a la posición n’ simétrica a través de m si n’ no tiene piezas. Encuentra una manera de mover las 3 piezas de x, y, z para que al final tengamos 3 piezas en u, v, w.
- Entrada: 6 números x, y, z y u, v, w. (-10^6 < x,y,z,u,v,w < 10^6)
-
Salida: K – número de pasos realizados. Las siguientes K líneas son las posiciones de las 3 piezas en cada paso.
Ejemplo:
– Entrada:
3 4 5 1 2 3
Actualmente hay 3 piezas de ajedrez en las posiciones 3,4,5, necesitamos moverlas a las posiciones 1,2,3.
– Salida:
2
3 2 5
3 2 1
El movimiento del ejemplo anterior
– Paso 0: 3 4 5
– Paso 1: Las posiciones 4 y 3 tienen piezas, mueve la pieza en la posición 4 a 2 (porque 2 es simétrico a 4 respecto a 3 y no hay piezas en 2) => 3, 2, 5
- Paso 2: Las posiciones 5 y 3 tienen piezas, mueve la pieza en la posición 5 a 1 (porque 1 es simétrico a 5 respecto a 3 y no hay piezas en 1) => 3, 2, 1
Nota:
– Mientras se obtengan 3 piezas en u, v, w, no es necesario devolver la pieza 1 a u, la pieza 2 a v y la pieza 3 a w.
- Puedes mover tantas veces como quieras.
Mi idea es utilizar la técnica de backtracking para examinar todos los casos. Pero (-10^6 <= u, v, w, a, b, c <= 10^6) por lo que mi algoritmo obtuvo TLE (tiempo de espera agotado).
¿Existe un enfoque mejor? Gracias a todos.
davy.ai
Un enfoque posible para resolver este problema es utilizar un algoritmo voraz. Podemos comenzar ordenando las posiciones iniciales de las tres piezas en orden ascendente. Luego, podemos intentar mover la pieza del medio (es decir, aquella con la posición mediana) hacia su posición final. Si la posición final es mayor que la posición mediana, repetidamente podemos mover la pieza hacia la derecha hasta que alcance su posición final. De lo contrario, repetidamente podemos mover la pieza hacia la izquierda hasta que alcance su posición final.
Una vez que la pieza del medio ha alcanzado su posición final, podemos enfocarnos en las otras dos piezas. Si una de ellas ya está en su posición final, podemos mover la otra pieza hacia su posición final. De lo contrario, podemos mover la pieza que está más cerca de su posición final hacia esa posición. Repetimos este proceso hasta que las tres piezas hayan alcanzado sus posiciones finales.
Este algoritmo garantiza encontrar una solución si existe una. Además, se ejecuta en tiempo O(1), lo cual es mucho más rápido que el enfoque de retroceso.