Juego con matrices


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C++

Durante la Olimpiada de Informática de Centroamérica y el Caribe (OICC), los organizadores quieren proponer un juego para los participantes.

El juego consiste en transformar una cuadrícula en otra utilizando la menor cantidad posible de movimientos. Se tienen dos cuadrículas de tamaño n \times n, ambas contienen los enteros del 1 al n^2, cada uno exactamente una vez, pero posiblemente en posiciones diferentes.

Para modificar una cuadrícula se permite realizar una de las siguientes operaciones cualquier número de veces (es posible no realizar ninguna operación):

  1. Intercambiar dos filas.
  2. Intercambiar dos columnas.

El objetivo del juego es transformar la primera cuadrícula en la segunda utilizando la menor cantidad posible de operaciones.

Entrada

La primera línea contiene un entero n (1 \le n \le 500) - el tamaño de las cuadrículas.

A continuación, se describen las n filas de la primera cuadrícula, cada una con n enteros.

Finalmente, se describen las n filas de la segunda cuadrícula, siguiendo el mismo formato.

Se garantiza que ambas cuadrículas contienen los enteros del 1 al n^2, cada uno exactamente una vez.

Salida

Imprime un entero k - la mínima cantidad de operaciones necesarias para transformar la primera cuadrícula en la segunda.

A continuación, imprime k líneas que describan las operaciones realizadas.

Cada operación debe tener uno de los siguientes formatos:

  • 1 a b: intercambiar las filas a y b.
  • 2 a b: intercambiar las columnas a y b.

Las filas y columnas están numeradas desde 1 hasta n.

Si no es posible transformar la primera cuadrícula en la segunda utilizando las operaciones permitidas, imprime únicamente -1.

Subtareas

Esta tarea está compuesta por 3 subtareas.

La puntuación de cada subtarea se determina de la siguiente manera:

  • Se otorgará el 100\% de los puntos si se proporciona una secuencia válida de operaciones que transforme la primera matriz en la segunda utilizando la cantidad mínima de operaciones, en todos los casos de prueba de la subtarea.
  • Se otorgará el 30\% de los puntos si la cantidad de operaciones indicada es correcta en todos los casos de prueba de la subtarea, independientemente de que la secuencia de operaciones sea válida.
  • Se otorgarán 0 puntos en caso contrario.
Subtarea Puntos Restricciones adicionales Dependencias
1 12 1 \le n \le 3 -
2 55 1 \le n \le 50 1
3 33 Sin restricciones adicionales 1-2

Ejemplos

Entrada 1
3
1 2 3
4 5 6
7 8 9
2 1 3
8 7 9
5 4 6
Salida 1
2
2 1 2
1 2 3
Entrada 2
3
6 3 7
8 1 4
9 2 5
8 5 2
7 3 1
9 4 6
Salida 2
-1

Comments

There are no comments at the moment.