Patrones de Pastoreo
¡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 metros por metros! El campo está distribuido como una cuadrícula de \(5×5\) cuadrados de metro por metro, siendo la ubicación del cuadrado superior izquierdo, y 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 cuadrados pelados ( par), los cuales no tienen pasto. Bessie, la vaca, comienza a pastear en el cuadrado el cual siempre tiene pasto, y Mildred, la vaca, comienza a pastear en el cuadrado 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 .
• Líneas 2…1+K: Cada línea contiene la ubicación de un cuadrado sin pasto proporcionado los dos enteros separados por espacio y .
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, indica la posición inicial de Bessie y 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 :
b b--b b--b
| | | | |
b--b b--b b
|
* * * * b/m
|
m--m--m--m--m
|
m--m--m--m--m
Comments