#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <limits.h>

/*
O labirinto pode ser modelado como um grafo, em que cada célula válida (caminho livre, ponto de partida ou saída) corresponde a um vértice, e movimentações
válidas entre células adjacentes correspondem às arestas do grafo. Como o problema do labirinto é geralmente relacionado a encontrar uma saída, partindo-se de
um determinado ponto de origem, ele pode ser interpretado como encontrar o menor caminho válido entre dois vértices de um grafo, o que pode ser feito em tempo
polinomial, ou seja, de forma eciente.
Para dar uma solução para o problema iremos aplicar os algoritmos de busca em
profundidade (DFS) e busca em largura (BFS). O labirinto deve ser fornecido a partir
de um arquivo .dat com uma matriz N × M contendo as seguintes possibilidades
para cada célula: 0 (caminho livre), 1 (parede), 2 (ponto de partida) e 3 (saída
do labirinto). Como ilustração, a seguir temos um exemplo de arquivo .dat e o
correspondente labirinto.

1111111111
1000000001
1200010101
1111010101
1000000101
1011111101
1000000001
1111111101
1100100001
1101001111
1000000001
1111111311

*/

typedef struct node* link;

typedef struct{
    int x;
    int y;
    int indice;
} vertice;

struct node{
    vertice destino;
    link next;
}; //peso de todos é 1 ou 0 (existe ou não existe)

typedef struct{
    link* listaAdj;
    int numVertices;
    vertice entrada;
    vertice saida;
} grafoLista;

//é possível chegar na saída com um único caminho.
//repetir caminhos não tem utilidade
//ciclos devem ser removidos

void adicionarFila(vertice* fila, unsigned int *fimFila, vertice entrada){
    fila[*fimFila] = entrada;
    *fimFila = *fimFila + 1;
}

vertice removerFila(vertice* fila, unsigned int *inicioFila){
    vertice aux = fila[*inicioFila];
    *inicioFila = *inicioFila + 1;
    return aux;
}

grafoLista* inicializarGrafo(int numVertices){

    grafoLista* grafo = malloc(sizeof(grafoLista));

    grafo->numVertices = numVertices;

    grafo->listaAdj = (link*)malloc(sizeof(link) * numVertices);

    for(int i = 0; i < grafo->numVertices; i++){
        grafo->listaAdj[i] = NULL;
    }

    return grafo;
}

void adicionarAresta(grafoLista* grafo, vertice origem, vertice destino){

    link novono = malloc(sizeof(struct node));
    novono->destino = destino;
    novono->next = grafo->listaAdj[origem.indice]; 
    grafo->listaAdj[origem.indice] = novono;

    if (origem.indice == 0)
        grafo->entrada = origem;
    if (destino.indice == 0)
        grafo->entrada = destino;

    if (origem.indice == grafo->numVertices - 1)
        grafo->saida = origem;
    if (destino.indice == grafo->numVertices - 1)
        grafo->saida = destino;

}

void solucaoLabirinto(vertice* pai, int numVertices, vertice entrada, vertice saida){
    unsigned int passos = 0;
    unsigned int coords[numVertices][2];
    for(vertice x = saida; x.indice != entrada.indice; x = pai[x.indice]){
        coords[passos][0] = x.x;
        coords[passos][1] = x.y;
        passos++;
    }
    coords[passos][0] = entrada.x;
    coords[passos][1] = entrada.y;

    printf("CAMINHO PERCORRIDO:\n");
    for (unsigned int i = passos; i > 0; i--){
         if (i == passos)
            printf("ENTRADA : (%d, %d)\n", coords[i][0], coords[i][1]);
        else if (i == 0)
            printf("SAIDA : (%d, %d)\n", coords[i][0], coords[i][1]);
        else
         printf("MOVIMENTO : (%u, %u)\n", coords[i][0], coords[i][1]);
    }
    printf("SAIDA : (%d, %d)\n", coords[0][0], coords[0][1]);
    
    printf("TAMANHO DO CAMINHO : %u\n", passos);

}

void BFS(grafoLista* grafo, vertice entrada, vertice saida){

    vertice fila[grafo->numVertices];
    vertice pai[grafo->numVertices];
    int distancia[grafo->numVertices];
    bool visitado[grafo->numVertices];
    unsigned int numPassos = 0;
    bool achouSaida = false; // incrementa numPassos enquanto nao encontrar a saida
    
    for(int i = 0; i < grafo->numVertices; i++)
    {
        fila[i].indice = 0;
        fila[i].x = 0;
        fila[i].y = 0;
        pai[i].indice = 0;
        pai[i].x = 0;
        pai[i].y = 0;
        visitado[i] = false;
        distancia[i] = INT_MAX;
    }

    unsigned int inicioFila = 0;
    unsigned int fimFila = 0;

    adicionarFila(fila, &fimFila, entrada);
    pai[entrada.indice] = entrada;
    distancia[entrada.indice] = 0;

    // mais de um caminho para a saida
    
    while(inicioFila < fimFila){
        
        vertice vertAtual = removerFila(fila, &inicioFila);

        if (!achouSaida)
            numPassos++;
        
        visitado[vertAtual.indice] = true;

        link p = grafo->listaAdj[vertAtual.indice];

        while(p != NULL){
            if (visitado[p->destino.indice] == false){
                visitado[p->destino.indice] = true; 
                if (p->destino.indice == saida.indice)
                    achouSaida = false;
                pai[p->destino.indice] = vertAtual;
                distancia[p->destino.indice] = distancia[vertAtual.indice] + 1;
                adicionarFila(fila, &fimFila, p->destino);
            }
            
            p = p->next;
        }

    }

    printf("SOLUCAO EM BFS:\n");
    for(int i = 0; i < grafo->numVertices; i++){ //+1 para fila, devido ao heap e arestas

        if (distancia[i] != INT_MAX)
            printf("VERTICE : [%d], DISTANCIA = %d", i, distancia[i]);
        else
            printf("VERTICE : [%d] NÃO É ALCANÇÁVEL", i);
        printf("\n");
    }

    solucaoLabirinto(pai, grafo->numVertices, entrada, saida);
    printf("PASSOS ATE ACHAR A SAIDA : %d\n", numPassos);
    
}


void DFS_visit(grafoLista* grafo, vertice* pai, vertice* vertices, int* distancia, bool* visitado, vertice vert, unsigned int *numPassos, bool *achouSaida, vertice saida){
    visitado[vert.indice] = true;
    vertices[vert.indice] = vert; // guarda o vertice visitado para poder acessa-lo em outros DFS_visit depois

    if (*achouSaida == false){
        *numPassos = *numPassos + 1;
    }
    
    link p = grafo->listaAdj[vert.indice];
    while(p != NULL){
        vertice vertAtual = p->destino;
        if (visitado[vertAtual.indice] == false){
            pai[vertAtual.indice] = vert;
            if (vertAtual.indice == saida.indice)
                *achouSaida = true;

            distancia[vertAtual.indice] = distancia[vert.indice] + 1;
            DFS_visit(grafo, pai, vertices, distancia, visitado, vertAtual, numPassos, achouSaida, saida);
        }

        p = p->next;
    }
}


void DFS(grafoLista* grafo, vertice entrada, vertice saida){
    vertice pai[grafo->numVertices]; // vetor dos pais de cada vertice usado no solucaoLabirinto()
    vertice vertices[grafo->numVertices]; // vetor que guarda os vertices encontrados para poder utilizar o DFS_visit()
    bool visitado[grafo->numVertices];
    int distancia[grafo->numVertices];
    unsigned numPassos = 0;
    bool achouSaida = false; // incrementa numPassos enquanto nao encontrar a saida

    for (int i=0; i < grafo->numVertices; i++){
        pai[i].indice = 0;
        pai[i].x = 0;
        pai[i].y = 0;
        vertices[i].indice = 0;
        vertices[i].x = 0;
        vertices[i].y = 0;
        visitado[i] = false;
        distancia[i] = INT_MAX;
    }
    distancia[entrada.indice] = 0;
    DFS_visit(grafo, pai, vertices, distancia, visitado, entrada, &numPassos, &achouSaida, saida);
    
    for (int i=1; i < grafo->numVertices; i++)
        if (visitado[i] == false && vertices[i].indice != 0)
            DFS_visit(grafo, pai, vertices, distancia, visitado, vertices[i], &numPassos, &achouSaida, saida);

    printf("SOLUCAO EM DFS:\n");
    for(int i = 0; i < grafo->numVertices; i++){ //+1 para fila, devido ao heap e arestas

        if (distancia[i] != INT_MAX)
            printf("VERTICE : [%d], DISTANCIA = %d", i, distancia[i]);
        else
            printf("VERTICE : [%d] NÃO É ALCANÇÁVEL", i);
        printf("\n");
    }

    solucaoLabirinto(pai, grafo->numVertices, entrada, saida);
    printf("PASSOS ATE ACHAR A SAIDA : %d\n", numPassos);
}


grafoLista *lerEntrada(char *filename){
    FILE* stream = fopen(filename, "r");

    if (stream == NULL){
        printf("Erro tentando abrir arquivo.\n");
        return NULL;
    }

    unsigned int n = 0; // tamanho horizontal da matriz
    unsigned int m = 0; // tamanho vertical da matriz
    char c = '1'; // char auxiliar lido durante o fread()

    // determinar tamanho horizontal da matriz (passar pela primeira linha até encontrar um '\n')
    while (c != '\n' && c != '\0'){
        if (fread(&c, sizeof(char), 1, stream)){
            if (c != '\n')
                n++;
        } else{
            printf("Arquivo vazio.\n");
            return NULL;
        }
    }

    rewind(stream); // resetar a cabeca de leitura pro comeco

    // determinar tamanho vertical da matriz (agora que sabemos o tamanho horizontal, podemos ficar movendo
    // a cabeca de leitura esse tanto varias vezes até encontrar o '\0')
    do{
        fseek(stream, n, SEEK_CUR);
        m++;
    } while (fread(&c, sizeof(char), 1, stream));

    rewind(stream);

    n++; // nosso algoritmo para calcular o horizontal desconsidera o '\n', porem ele ainda esta la na matriz
    
    char matriz[m][n];
    fread(matriz, sizeof(char), n * m, stream);

    n--; // proximas operacoes nao precisam considerar os \n


    // determinar o numero de vertices
    unsigned int numVertices = 0;
    for (unsigned int i=0; i < m; i++){
        for (unsigned int j=0; j < n; j++){
            if (matriz[i][j] == '1')
                continue;
            else
                numVertices++;
        }
    }

    
    // encontrar as coordenadas de cada vertice de acordo com seu indice
    unsigned int coords[numVertices][2]; // coords[v][0] = x, coords[v][1] = y
    unsigned int aux = 1; // indice do vertice atual
    for (unsigned int i=0; i < m; i++){
        for (unsigned int j=0; j < n; j++){
            if (matriz[i][j] == '1')
                continue;
            else{
                switch(matriz[i][j]){
                    case '2':
                        coords[0][0] = j;
                        coords[0][1] = i;
                        break;
                    case '0':
                        coords[aux][0] = j;
                        coords[aux][1] = i;
                        aux++;
                        break;
                    case '3':
                        coords[numVertices - 1][0] = j;
                        coords[numVertices - 1][1] = i;
                        break;
                    default:
                        break;
                }
            }
        }
    }



    // gerar o grafo de acordo com as coordenadas e os indices
    grafoLista* grafo = inicializarGrafo(numVertices);
    for (unsigned int i=0; i < numVertices; i++){
        for (unsigned int j=0; j < numVertices; j++){
            // if (for adjacente)
            if (((coords[i][0] == coords[j][0] - 1 || coords[i][0] == coords[j][0] + 1) && coords[i][1] == coords[j][1]) ||
                ((coords[i][1] == coords[j][1] - 1 || coords[i][1] == coords[j][1] + 1) && coords[i][0] == coords[j][0])
               ){
                vertice origem;
                origem.indice = i;
                origem.x = coords[i][0];
                origem.y = coords[i][1];

                vertice destino;
                destino.indice = j;
                destino.x = coords[j][0];
                destino.y = coords[j][1];

                adicionarAresta(grafo, origem, destino);
            }
        }
    }

    return grafo;
}

int main(){

    int numVertices = 8; 

    grafoLista* grafo = lerEntrada("teste.dat");

    BFS(grafo, grafo->entrada, grafo->saida);
    printf("\n");
    DFS(grafo, grafo->entrada, grafo->saida);
}