#include <stdio.h>
#include <windows.h>
/***************************ROBOEX.C**************************************
 Semplice Labirinto con Animazione E allocazione dinamica delle matrici
                         (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 rTarget=-1, cTarget=-1;

int Delay = 1;//Animation (ms)

int MazeRows = 0;
int MazeCols = 0;

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

const char chDrawWall =  (char)219;
const char chDrawTarget =  (char)219;
const char colorTarget =  91;

void putcColor(int ch, int color)
{
	HANDLE hOutput = GetStdHandle(STD_OUTPUT_HANDLE);
	SetConsoleMode(hOutput, ENABLE_PROCESSED_OUTPUT | ENABLE_VIRTUAL_TERMINAL_PROCESSING);
	printf("\033[%dm%c\033[0m",color,ch); 
}

//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 chWall://Disegno il muro...
					printf("%c", chDrawWall);//(char)219); //... con un quadrato pieno
					break;
				default:{
					printf("%c", Maze[r][c]);
					if(r==rTarget && c==cTarget)
						putcColor(chDrawTarget,colorTarget);//printf("\033[%dm %3d\033[m", r, c);//printf("%c",chDrawTarget);
				}
            }
        }
        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)
    {
		for (r = 0; r < MazeRows; r++){
			for (c = 0; c < MazeCols; c++){
				if(Maze[r][c]=='0'){
					sr=r;sc=c;
					break;
				}
			}
			if (sr>=0 && sc>=0)
				break;
		}
		       
		for (r = 0; r < MazeRows; r++){
			for (c = 0; c < MazeCols; c++){
				if(Maze[MazeRows-r-1][MazeCols-c-1]=='0'){
					er=MazeRows-r-1;ec=MazeCols-c-1;
					break;
				}
			}
			if (er>=0 && ec>=0)
				break;
		}
    }
	if (sr < 0 || sc < 0 || er < 0 || ec < 0)
		return 0;
    *rs = sr; *cs = sc; *rt = er, * ct = ec;
    return 1;
}

char** LoadMaze(int *pnr, int *pnc){
	char buff[512];
	char **matrix = NULL;
	int nr=0,nc=0,kc=0;
	while(gets(buff)){
		kc=strlen(buff);
		if(nc>0 && kc !=nc){
			fprintf(stderr,"Error Not a Matrix");
			return NULL;
		}
		nc=kc;
		nr++;
	}
	rewind(stdin);
	
	nr++;
	nc++;
	matrix = malloc(nr * sizeof(char *));
	matrix[nr]=0;
	for(int i=0; i < nr; i ++){
		matrix[i] = malloc(nc * sizeof(char));
		gets(matrix[i]);
	}
	*pnr=nr-1;
	*pnc=nc-1;
	return matrix;

}

int main(int argc, char* argv[])
{
	char** Maze=0;
	int nr=0,nc=0;
	Maze=LoadMaze(&nr,&nc);

    int rStart, cStart;
    //Calcolo Numero di righe e colonne del labirinto
    MazeRows = 0;
	while(Maze[MazeRows])
		MazeRows++;
    MazeCols = strlen(Maze[0]);
	--MazeRows;
    if (!FindStartTarget(Maze, &rStart, &cStart, &rTarget, &cTarget))
    {
        printf("\nMissing Start/Target item\n");
        return -1;
    }
	
	for(int i=0; i < nr; i ++){
		for(int j=0; j < nc; j ++)
			Maze[i][j] = (Maze[i][j]=='0'?  chFree: chWall );
	}

    //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;
}