#include <stdio.h>

/*************ROBOEX.C*******************
 Semplice Labirinto con Animazione
                  (Fischetti P.)
****************************************/
//////https://www.cs.bu.edu/teaching/alg/maze/
#include <stdio.h>
#include <io.h>
#include <windows.h>
#include <stdio.h>
#include <conio.h>

int Delay = 100;//Animation (ms)

int MazeRows = 0;
int MazeCols = 0;

const char chStart = '2'; //Cella di Partenza
const char chTarget = '3'; // Cella obiettivo
const char chWall = '#'; //Cella Muro
const char chFree = ' '; //Cella Libera
const char chRobot = '*'; //Il Robot

//Visualizza il Labirinto
void PrintMaze(char *Maze[])
{
    int r, c;
    system("CLS");
    for (r = 0; r < MazeRows; r++)
    {
        for (c = 0; c < MazeCols; c++)
        {
            switch (Maze[r][c])
            {
            case '#'://Disegno il muro...
                printf("%c", (char)219); //... con un quadrato pieno
                break;
            default:
                printf("%c", Maze[r][c]);
            }
        }
        printf("\n");
    }
    printf("\n");
}

//Algoritom di risoluzione ricorsivo
int Solve(char *Maze[],int r, int c, int  rTarget, int cTarget)
{
    Maze[r][c] = chRobot;

    if (Delay > 0)
    {
        PrintMaze(Maze);
        Sleep(Delay);
    }

    // Target Raggiunto?.
    if (r == rTarget && c == cTarget)
    {
        return 1;
    }

    // Ricerca Ricorsiva...
    //UP
    if (r > 0 && Maze[r - 1][c] == chFree && Solve(Maze,r - 1, c, rTarget, cTarget))
    {
        return 1;
    }
    //LEFT
    if (c > 0 && Maze[r][c - 1] == chFree && Solve(Maze,r, c - 1, rTarget, cTarget))
    {
        return 1;
    }
    //DOWN
    if (r < MazeRows - 1 && Maze[r + 1][c] == chFree && Solve(Maze,r + 1, c, rTarget, cTarget))
    {
        return 1;
    }
    //RIGHT
    if (c < MazeCols - 1 && Maze[r][c + 1] == chFree && Solve(Maze,r, c + 1, rTarget, cTarget))
    {
        return 1;
    }

    // Cerco un'altra strada.
    Maze[r][c] = chFree;

    if (Delay > 0)
    {
        //Anim
        PrintMaze(Maze);
        Sleep(Delay);
    }
    return 0;
}

//Cerco le coordinate della cella di partenza e di arrivo
int FindStartTarget(char *Maze[],int* rs, int* cs, int* rt, int* ct)
{
    int sr = -1;
    int sc = -1;
    int er = -1;
    int ec = -1;
    int r, c;
    for (r = 0; r < MazeRows; r++)
        for (c = 0; c < MazeCols; c++)
        {
            if (chStart == Maze[r][c])
            {
                sr = r;
                sc = c;
                Maze[r][c] = chFree;
            }
            else if (chTarget == Maze[r][c])
            {
                er = r;
                ec = c;
                
                Maze[r][c] = chFree;
            }
        }

    if (sr < 0 || sc < 0 || er < 0 || ec < 0)
    {
        return 0;
    }
    *rs = sr; *cs = sc; *rt = er, * ct = ec;
    return 1;
}



int main(int argc, char* argv[])
{
    char* Maze[] =
    {
        _strdup("#2#######"),
        _strdup("#   #   #"),
        _strdup("# ### # #"),
        _strdup("# #   # #"),
        _strdup("# # # ###"),
        _strdup("#   # # #"),
        _strdup("# ### # #"),
        _strdup("#   #   #"),
        _strdup("###     #"),
        _strdup("#######3#")
    };

    int rStart, cStart, rTarget, cTarget;
    //Calcolo Numero di righe e colonne del labirinto
    MazeRows = sizeof(Maze) / sizeof(Maze[0]);
    MazeCols = strlen(Maze[0]);
    if (!FindStartTarget(Maze, &rStart, &cStart, &rTarget, &cTarget))
    {
        printf("\nMissing Start/Target item\n");
        return -1;
    }

    //Posizionamento iniziale del robot	
    Maze[rStart][cStart] = chRobot;
    PrintMaze(Maze);
    printf("Premere un tasto per iniziare...");
    _getch();
    if (Solve(Maze,rStart, cStart, rTarget, cTarget))
    {
        PrintMaze(Maze);
        printf("OK");
    }
    else
    {
        printf("\nFail!!!\n");
    }

    return 0;
}