#include <stdio.h>
#include <stdlib.h>
#include "../include/labyrinth.h"
#include "../include/dfs.h"

short dfs_r(Labyrinth* labyrinth, int i, int j);

void dfs(Labyrinth* labyrinth){
    dfs_r(labyrinth, labyrinth->start.x, labyrinth->start.y);
    find_path(labyrinth);
}

short dfs_r(Labyrinth* labyrinth, int i, int j){
    if(i==labyrinth->end.x && j==labyrinth->end.y)
        return 1;
    
    if(i!=labyrinth->start.x || j!=labyrinth->start.y)
        labyrinth->at[i][j].color = GREEN;

    printLab(labyrinth);

    labyrinth->at[i][j].visited = 1;
    
    // randomly generates order of direction to try
    int arr[4] = {0, 1, 2, 3}, tmp, tp;
    for(int h=3; h>0; h--){
        tmp = rand()%h;
        tp = arr[h];
        arr[h] = arr[tmp];
        arr[tmp] = tp;
    }

    // goes in the direction if possible
    for(int h=0; h<4; h++){
        if(arr[h]==0){
            if(i>0 && labyrinth->at[i-1][j].south && !labyrinth->at[i-1][j].visited){
                labyrinth->at[i-1][j].color = ORANGE;
                labyrinth->at[i-1][j].direction = UP;
                if(dfs_r(labyrinth, i-1, j))
                    return 1;
            }
        }else if(arr[h]==1){
            if(j<labyrinth->y_size-1 && labyrinth->at[i][j].east && !labyrinth->at[i][j+1].visited){
                labyrinth->at[i][j+1].color = ORANGE;
                labyrinth->at[i][j+1].direction = RIGHT;
                if(dfs_r(labyrinth, i, j+1))
                    return 1;
            }
        }else if(arr[h]==2){
            if(i<labyrinth->y_size-1 && labyrinth->at[i][j].south && !labyrinth->at[i+1][j].visited){
                labyrinth->at[i+1][j].color = ORANGE;
                labyrinth->at[i+1][j].direction = DOWN;
                if(dfs_r(labyrinth, i+1, j))
                    return 1;
            }
        }else if(arr[h]==3){
            if(j>0 && labyrinth->at[i][j-1].east && !labyrinth->at[i][j-1].visited){
                labyrinth->at[i][j-1].color = ORANGE;
                labyrinth->at[i][j-1].direction = LEFT;
                if(dfs_r(labyrinth, i, j-1))
                    return 1;
            }
        }
    }
    
    return 0;
}