Caminos en la grilla


Submit solution


Points: 100 (partial)
Time limit: 2.0s
Memory limit: 1G

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

Hay una matriz con H filas horizontales y W columnas verticales. Sea (i, j) el cuadrado en la i-ésima fila desde la parte superior y la j-ésima columna de la izquierda.

Para cada i y \(j (1\lei\leH, 1\lej\leW)\), el cuadrado (i, j) se describe mediante un carácter a_{i, j}. Si a_{i, j} es \("."\) , el cuadrado (i, j) es un cuadrado vacío; si a_{i, j} es \("\#"\), el cuadrado (i, j) contiene una pared. Se garantiza que los cuadrados (1,1) y (H, W) son cuadrados vacíos.

Taro partirá desde Cuadrado (1,1) y quiere alcanzar (H, W) moviéndose repetidamente hacia la derecha o hacia abajo hasta un cuadrado vacío adyacente.

Busque el número de caminos diferentes de Taro desde el cuadrado (1,1) a (H, W). Como la respuesta puede ser extremadamente grande, calculela módulo 10^9 + 7.

Restricciones:

  • H y W son enteros.
  • 2 \le H, W \le 1000
  • a_{i, j} es \("."\) o \("\#"\) .
  • Cuadrados (1,1) y (H, W) son cuadrados vacíos.

Entrada:

La primera línea de entrada contendrá H y W.

Luego siguen H líneas cada una conteniendo W enteros. El entero en la línea i y la columna j indica a_{i,j}.

Salida:

Imprime el número de caminos de Taro desde Cuadrado (1,1) a (H, W), módulo 10^9 + 7.

Entrada de ejemplo 1:

3 4
... #
. # ..
....

Salida de ejemplo 1:

3

Los tres caminos son los siguientes:

Descripcion

Entrada de ejemplo 2:

5 2
.. 
#.
.. 
.#
..

Salida de ejemplo 2:

0

No hay ningún camino.

Entrada de ejemplo 3:

 5 5
..#..
.....
#...#
.....
..#..

Salida de ejemplo 3:

24

Entrada de ejemplo 4:

20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................    
....................
....................
....................

Salida de ejemplo 4:

345263555

Comments

There are no comments at the moment.