Laberinto 0-K

Tiempo máximo: 1000 ms

Memoria máxima: 30000 KB

Dificultad: Medio (45)

En este problema, se te da un laberinto rectangular compuesto por celdas libres y muros. Tu objetivo es determinar el mínimo número de muros que debes atravesar para llegar desde la esquina superior izquierda hasta la esquina inferior derecha del laberinto. Cada movimiento puede hacerse a una celda adyacente en las cuatro direcciones: arriba, abajo, izquierda o derecha. Moverse a una celda libre no tiene coste, mientras que moverse a un muro incrementa tu coste en 1.

Entrada

La primera línea contiene dos enteros \(n\) y \(m\) (\(1 \le n, m \le 1000\)), que representan el número de filas y columnas del laberinto. Las siguientes \(n\) líneas contienen cada una \(m\) caracteres:

Un punto representa una celda libre.
Una almohadilla representa un muro.

Salida

Una sola línea con un entero: el mínimo número de muros que deben ser atravesados para ir desde la esquina superior izquierda hasta la esquina inferior derecha.

Ejemplos

Ejemplo 1

Entrada

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

Salida

Ejemplo 2

Entrada

6 7
.######
#######
###.###
##..###
#######
######.

Salida

ID	Usuario	Lenguaje	Veredicto	Tiempo	Memoria	Fecha

#	ID	Usuario	Lenguaje	Veredicto	Tiempo	Memoria	Fecha