Patrones de Pastoreo


Submit solution

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

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, VB

¡Debido a recientes recortes de presupuesto, GJ ha disminuido su granja de tal forma que el área para sus vacas es únicamente un campo de 5 metros por 5 metros! El campo está distribuido como una cuadrícula de \(5×5\) cuadrados de 1 metro por 1 metro, siendo (1,1) la ubicación del cuadrado superior izquierdo, y (5,5) la ubicación del cuadrado inferior derecho:

(1,1) (1,2) (1,3) (1,4) (1,5)
(2,1) (2,2) (2,3) (2,4) (2,5)
(3,1) (3,2) (3,3) (3,4) (3,5)
(4,1) (4,2) (4,3) (4,4) (4,5)
(5,1) (5,2) (5,3) (5,4) (5,5)

Cada cuadrado en esta cuadrícula está lleno de delicioso pasto, excepto para K cuadrados pelados (0 \leq K \leq 22, K par), los cuales no tienen pasto. Bessie, la vaca, comienza a pastear en el cuadrado (1,1) el cual siempre tiene pasto, y Mildred, la vaca, comienza a pastear en el cuadrado (5,5) el cual también siempre tiene pasto.

Cada media hora, Bessie y Mildred terminan de comer en sus respectivos cuadrados y ambas se mueven a cuadrados con pasto adyacentes (norte, sur, este u oeste). Ellas quieren consumir todos los cuadrados con pasto y terminar exactamente en la misma ubicación final. Por favor calcule el número de maneras diferentes en que esto puede pasar. Bessie y Mildred siempre se mueven a cuadrados con pasto, y nunca se mueven hasta el mismo cuadrado a menos que sea el último cuadrado con pasto restante.

Entrada

• Línea 1: El entero K.

• Líneas 2…1+K: Cada línea contiene la ubicación (i, j) de un cuadrado sin pasto proporcionado los dos enteros separados por espacio i y j.

Ejemplo de Entrada

4
3 2
3 3
3 4
3 1

Detalles de la Entrada

La cuadrícula inicial se ve como esto (donde '•' denota un cuadrado con pasto, '*' denota un cuadrado sin pasto, b indica la posición inicial de Bessie y m indica la posición inicial de Mildred.

b  .  .  .  .
.  .  .  .  .
*  *  *  *  .
.  .  .  .  .
.  .  .  .  m

Salida

• Línea 1: El número de maneras diferentes en que Bessie y Mildred pueden recorrer el campo para comer todo el pasto y terminar en la misma ubicación final.

Ejemplo de Salida

1

Detalles de la Salida

Hay una solución posible, con Bessie y Mildred encontrándose en el cuadrado (3,5):

b  b--b  b--b
|  |  |  |  |
b--b  b--b  b
            |
*  *  *  * b/m
            |
m--m--m--m--m
|
m--m--m--m--m

Comments

There are no comments at the moment.