Rat_In_Maze_All_Solutions

#include<stdio.h>

//Tamaño del laberinto
#define N 4
int verif=0;//booleano que me permite saber si hay solucion o no

int solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);

/* funcion que imprimirá mi solución */
void printSolution(int sol[N][N])
{
    int i,j;
    for ( i = 0; i < N; i++)
    {
        for ( j = 0; j < N; j++)
            printf(" %d ", sol[i][j]);
        printf("\n");
    }
}

/* verifica si es  segura la casilla */
int isSafe(int maze[N][N], int x, int y)
{

    if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
        return 1;

    return 0;
}

/*Esta funcion en si no ayuda mucho, solo permite saber si hubo solucion o no*/
int solveMaze(int maze[N][N])
{
    int sol[N][N] = { {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0}
    };

    if(solveMazeUtil(maze, 0, 0, sol) == 1)
    {
        printf("----");
        return 0;
    }
    if (verif==0){
        printf("No existe solucion");
    }


    return 1;
}

/*Funcion Backtrack*/
int solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
    // Caso Base
    if(x == N-1 && y == N-1)
    {
        sol[x][y] = 1;
        printSolution(sol);//imprimo solucion
        printf("\n");
        verif=1;//se encontro solucion
        return 1;


    }

    // verifico si es valido
    if(isSafe(maze, x, y) == 1)
    {
        // si es valido, marco esta casilla como parte de mi camino
        sol[x][y] = 1;int p;

        /* Me muevo hacia la direccion x permitida*/
        if (solveMazeUtil(maze, x+1, y, sol) == 1)
            p=1;//Si aqui pusiera return 1 , solo botaria una solucion

        /* Me muevo hacia la direccion y permitida */
        if (solveMazeUtil(maze, x, y+1, sol) == 1)
            p=1;

        /* Si no llego a alguna solucion, mi camino que tome no es valido,
         * vuelvo y pruebo otro camino*/
        sol[x][y] = 0;
        return 0;
    }

    return 1;
}


int main()
{
    int maze[N][N]  =  { {1, 0, 0, 0},
        {1, 1, 1, 1},
        {0, 1, 1, 0},
        {1, 1, 1, 1}
    };

    solveMaze(maze);
    getchar();
    return 0;
}