Estás desarrollando una aplicación para ayudar a personas con visibilidad reducida. Has implementado diferentes funcionalidades: GPS, sensor de proximidad, reconocimiento de voz, etc.
Solo te falta implementar una única tarea: dada la posicición del usuario en un mapa, y los obstáculos que tiene a su alrededor, determinar en cuántas posiciones diferentes es posible acabar tras dar un determinado número de pasos.
Entrada
La primera línea contendrá el número de filas y columnas del mapa \((1 \le n, m \le 50)\), respectivamente.
Después, aparecerá un mapa de \(n\) filas y \(m\) columnas. Las celdas vacías estarán representadas por espacios en blanco, y las celdas obstaculizadas estarán representadas por almohadillas. La posición inicial del usuario estará denotada por una única 'S'.
Finalmente, aparece un número entero \((1 \le k \le 1000)\) que representa el número de pasos que dará el usuario (el usuario se puede mover en cada paso a la izquierda, derecha, arriba y abajo).
Salida
En una única línea, el número de lugares posibles en los que puede acabar el usuario tras dar exactamente \(k\) pasos.