Viaje vacuno


Submit solution

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

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Python, Swift, VB

Buscando por el mejor pasto, las vacas están paseando en el pastizal el cual está representado como una cuadricula con N filas y M columnas (2 \leq N \leq 100, 2 \leq M \leq 100). Siendo un observador agudo, el Granjero Juan ha registrado la posición de Bessie como (R1, C1) en cierto momento y luego como (R_2, C_2) exactamente T (0 < T \leq 15) segundos después. El no está seguro si ella pasó a través de (R_2, C_2) antes de los T segundos, pero él sabe que ella está ahí en el tiempo T.

GJ quiere un programa que use esta información para calcular un entero S que es el número de maneras que una vaca puede ir de (R_1, C_1) a (R_2, C_2) en exactamente T segundos. En cada segundo, una vaca puede desplazarse de cualquier posición a una posición vecina vertical u horizontalmente en el pastizal (no hay descanso para las vacas). Por supuesto, el pastizal tiene árboles por los que ninguna vaca puede pasar.

Dado un mapa con '.'s para espacios abiertos y '*'s para árboles, calcule el número de posibles maneras de ir de (R_1, C_1) a (R_2, C_2) en T segundos.

Entrada

  • Línea 1: Tres enteros separados pro espacios: N, M y T

  • Líneas 2..N+1: La línea i+1 describe la fila i del pastizal con exactamente M caracteres, cada uno de los cuales es un '.' o un '*'

  • Línea N+2: Cuatro enteros separados por espacios: R_1, C_1, R_2, y C_2.

Ejemplo de Entrada

4 5 6
...*.
...*.
.....
.....
1 3 1 5

Detalles de la Entrada

El pastizal tiene 4 filas y 5 columnas. La vaca va de la fila 1, columna 3 a la fila 1, columna 5, lo cual le toma exactamente 6 segundos.

Salida

Una sola línea con el entero S antes descrito

Ejemplo de Salida

1

Detalles de la Salida

Hay solamente un camino de (1, 3) a (1, 5) en exactamente 6 segundos (y es obvio que es uno que rodea los dos árboles).


Comments

There are no comments at the moment.