Hola

Me podrian ayudar con el algoritmo de este ejercicio que nose como hacerlo.


Un laberinto viene dado por una matriz cuadrada de tamaño nxn en la que cada posición puede ser un 0, un 1 o un asterisco. Un 1 significa que el camino está bloqueado, un 0 significa que el camino está abierto y un asterisco significa que el camino está abierto y además ganamos premio. En un laberinto puede haber como máximo un asterisco pero no es obligatorio que lo haya. En el laberinto se puede avanzar en cualquier dirección (horizontal, vertical y diagonal), siempre que el camino no esté bloqueado, a una posición vecina. Se pide un programa que comenzando en la posición (1,1) de la matriz (esquina superior izquierda), las filas y columnas comienzan a numerarse en 1, intente encontrar un camino a la posición (n,n), (esquina inferior derecha) .

El programa tomará como entrada un entero n en una línea y a continuación la matriz del laberinto dada en n líneas cada una con n valores binarios seguidos. Una de esas posiciones puede ser un asterisco; n será un entero positivo almacenable en un int, y devolverá la cadena "SI, CON PREMIO" si hay un camino directo (sin recorrer dos veces una misma posición) posible en el laberinto de salida que pasa por una posición con premio, "SI, SIN PREMIO" si hay algún camino en el laberinto de salida pero ninguno de los existentes pasa por una casilla con premio y "NO" sino hay camino posible de salida del laberinto. Cada salida terminará con un final de línea.

Ejemplo

Entrada

3

010

000

010

Salida

"SI, SIN PREMIO"

Saludos