/*************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;
#define MazeCols  9

//Il labirinto: 
//	2 la cella di partenza
//	3 la cella di arrivo
//	# muri
//N.B. il numero di righe non e' specificato viene calcolato nel main
char Maze[][MazeCols+1] = 
{
    "#2#######",
    "#   #   #",
    "# ### # #",
    "# #   # #",
    "# # # ###",
    "#   # # #",
    "# ### # #",
    "#   #   #",
    "#######3#",
};
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(void ) 
{
    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(int r, int c, int  rTarget, int cTarget)
{
    Maze[r][c] = chRobot;
    
    if(Delay > 0)
    { 
     PrintMaze();
     Sleep(Delay);
    }

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

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

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

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

//Cerco le coordinate della cella di partenza e di arrivo
int FindStartTarget(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[])
{
    int rStart,cStart,rTarget,cTarget;
    //Calcolo Numero di righe del labirinto
    MazeRows = sizeof(Maze) / sizeof(Maze[0]);
    if (!FindStartTarget(&rStart,&cStart,&rTarget,&cTarget))
    {
	printf("\nMissing Start/Target item\n");
	return -1;
    }

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

    return 0;
}