3019 - Guinea Rats Asia - Dhaka - 2004/2005
	PDF	PostScript	Submit	Ranking

Las ratas al igual que muchos otros roedores se utilizan en los laboratorios para experimentos científicos. Pero, a diferencia de muchos crueles experimentos quirúrgicos en nuestro experimento las ratas sería un gratificante psicológico. Nosotros estamos tratando de establecer el hecho de que las ratas tienen un buen mapa cognoscitivo en el cerebro que ellos tienen un buen sentido de direcciones. Aquí nos gustaría dar una prueba empírica para apoyar nuestro reclamo.

En nuestro experimento, nosotros construimos un laberinto para nuestras ratas. Este laberinto es básicamente una malla rectangular de celdas. Hay túneles que conducen de una celda a otra. Debido al arreglo rectangular, los túneles se pueden ejecutar en las cuatro direcciones principales. Desde la celda en la localización (i, j) las ratas pueden ir a Oriente (i, j + 1), Occidente (i, j - 1), Norte (i - 1, j) y Sur (i + 1, J), como se indica en la figura de la derecha.

Estos túneles están dirigidos. Así, un túnel que toma una rata a partir de (i, j) a (i, j - 1) no necesariamente proporciona un camino para volver a la celda (i, j). Algunos de estos túneles son de composición abierta, si una rata pasa por ese túnel, resultaría del laberinto. Ahora nosotros atraemos a las ratas, poniendo retazos de queso en determinadas celdas. Nuestro experimento exige entrenar a las ratas para recordar la sucesión de E (Este), W (Oeste), N (Norte), S (Sur) movimientos que los llevan a los cortes de queso.

Nosotros entrenamos una rata soltándolo en una celda en la salida designada del laberinto. A continuación pasa por el laberinto a su propia voluntad - tomando el EWNS se vuelve caprichosamente. Pero en algún momento se ve obligada a perder su vigor y detener el movimiento.  Entonces nosotros sacamos la rata del laberinto. Si se detuviera en una celda que contuvo un corte de queso nosotros lo premiamos con otro queso cortado, mientras deja el original en el laberinto; pero si detiene en una celda que no tiene queso cortado, habrá fracasado. Uno puede preguntarse lo que pasaría si la rata resulta de la tabla siguiendo un túnel abierto. Nuestra explicación es simple, nosotros pusimos el recorte de queso en algunas celdas particulares del laberinto no hay recortes queso en el mundo exterior. Así si una rata cae no consigue cualquier tipo de queso. 

Nosotros hemos visto que después de entrenar una rata varios tiempos de esta manera él parece recordar las sucesiones del movimiento premiándolo correctamente. Nuestro experimento requiere que nosotros soltemos a la rata en la misma celda de arranque y los cortes de queso se ponen en exactamente las mismas celdas cada vez que nosotros lo pusimos en el laberinto. Por lo tanto, si la rata considera que algunos  `` EESSWNNS" lo lleva a un corte de queso, siempre encontraría un corte de queso con esa sucesión de movimientos. Nuestra rata inteligente sólo necesita diferenciar los movimientos enriquecedores de los que no son. Sin embargo, su tarea no es tan simple como eso.

Nosotros planeamos entrenar nuestra rata en un laberinto y probar su habilidad de aprendizaje en un laberinto diferente. Pero para hacer que nosotros necesitamos asegurarnos que estos dos laberintos son idénticos. Para nuestro propósito los laberintos idénticos no necesariamente significan los laberintos idénticamente construidos. Lo que nosotros necesitamos es que ellos serían idénticos a las ratas. Si una rata tiene una sucesión de movimientos que llevan a un corte de queso en los entrenamientos están perplejo, también conseguiría un corte de queso con la misma sucesión de movimientos en el nuevo laberinto. Y si una sucesión de primacías de los movimientos a nada en el entrenamiento está perpleja, la misma sucesión debe ser ingrata para la rata en el nuevo laberinto. Esto es donde nosotros necesitamos su ayuda. Su tarea es tomar la configuración de los dos laberintos como la entrada, y nos dice si ellos son idénticos de la perspectiva de las ratas.

Input

El archivo de entrada contiene varios casos de prueba. La primera línea de la entrada le da el número de casos de prueba, T(1<= T<= 25). Entonces T pares de la configuración del laberinto a seguir. La primera línea de un laberinto de configuración se inicia con la dimensión - el número de filas R (1 R 20) y el número de columnas C (1<= C<=20) para el laberinto. Cada una de las siguiente R líneas se describen en las celdas C en esa columna. Cada celda está representada por un número de 4-bit (los números en el rango de 0 a 15). Estas cifras nos permiten una lista de todos los túneles de salida posible. La salida de los túneles del Norte, Este, Sur y Oeste están representados por la 0^th, 1^st, 2^nd and 3^rd bits respectivamente. Si algo se pone en cero el túnel en esa dirección está abierto el líder de rata esta fuera del laberinto, mientras que un bit indica que la rata puede ir a la siguiente celda en ese sentido. Tenemos etiqueta las celdas en el laberinto en el orden de fila a partir de 0. Tras la designación del laberinto de celdas, la línea siguiente le daría la etiqueta de la celda a partir de ese laberinto. El primer entero en la línea siguiente le daría el número de células que contienen los cortes de queso. Luego de que muchos de celdas etiquetas seguirán en la misma línea. Tal vez le resulte útil para relacionar las imágenes en la ilustración del segundo ejemplo de entrada.

Output

Para cada conjunto de entradas imprimir los números de casos de prueba  en primer lugar. Entonces de imprimir ‘sí’ si nuestra rata encuentra el par de laberintos que son idénticos, de lo contrario imprimirá ‘no’. Las secciones de muestra de entrada / salida debe aclarar el formato.

Sample Input

2
3 3
6 4 0
2 10 0
3 11 8
1
3 4 7 8
2 3
6 4 4
2 10 1
1
2 0 4
3 3
6 4 0
2 10 0
3 11 8
0
3 4 7 8
2 3
6 12 4
2 10 1
1
2 0 4

Sample Output

Case 1: Yes
Case 2: No
 


Illustration: Las siguientes imágenes ilustran la segunda muestra de prueba. Los números en las celdas indican las celdas etiquetadas, la rata se muestra a partir de celdas y los cortes de queso muestran que las celdas contienen los cortes de queso. En el primer laberinto la rata cae fuera del laberinto si se le lleva obligado pasar al oeste, por lo tanto, no recibe ningún queso. Pero en el segundo un laberinto un movimiento por el oeste se obligado a ganar un queso cortado.
 
 
 

---

Dhaka 2004-2005

Traducido por: Hugo César López Jorge