labirinto.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TAM 10

void push(int stack[], int *counter, int x)
{
    stack[*counter] = x;
    (*counter)++;
}

int pop(int stack[], int *counter)
{
    int result = stack[*counter - 1];
    (*counter)--;
    return result;
}

int pathfinder_Iterative(char maze[10][10], int start_col, int start_row)
{
    int stack[256];
    bool marked[256];
    int parent[256];
    int counter = 0;
    int start = start_row * 10 + start_col;
    int final_pos = -1;

    for (int i = 0; i < 256; i++)
    {
        marked[i] = false;
        parent[i] = -1;
    }
    marked[start] = true;
    push(stack, &counter, start);
    int dRow[4] = {-1, 1, 0, 0};
    int dCol[4] = {0, 0, -1, 1};
    while (counter > 0)
    {
        int pos = pop(stack, &counter);
        int row = pos / 10;
        int col = pos % 10;
        if (maze[row][col] == 'S')
        {
            final_pos = pos;
            break;
        }

        for (int i = 0; i < 4; i++)
        {
            int nc = col + dCol[i];
            int nr = row + dRow[i];

            if (nr < 0 || nr >= 10 || nc < 0 || nc >= 10)
            {
                continue;
            }
            if (maze[nr][nc] == '#' || maze[nr][nc] == 'E')
            {
                continue;
            }
            int new_pos = nr * 10 + nc;

            if (marked[new_pos])
            {
                continue;
            }

            marked[new_pos] = true;
            parent[new_pos] = pos;
            push(stack, &counter, new_pos);
        }
    }
    if (final_pos == -1)
    {
        return -1;
    }

    int curr = final_pos;
    while (parent[curr] != -1)
    {
        int r = curr / 10;
        int c = curr % 10;

        if (maze[r][c] != 'S' && maze[r][c] != 'E')
            maze[r][c] = 'x';
        curr = parent[curr];
    }
    return 0;
}

int encontrar_E(char lab[TAM][TAM], int *linha_E, int *coluna_E)
{
    int i, j;

    for (i = 0; i < TAM; i++)
    {
        for (j = 0; j < TAM; j++)
        {
            if (lab[i][j] == 'E')
            {
                *linha_E = i;
                *coluna_E = j;
                return 1;
            }
        }
    }
    return 0; // sem entrada
}

bool caminho(char lab[TAM][TAM], int linha, int coluna)
{
    if (linha < 0 || linha >= TAM || coluna < 0 || coluna >= TAM)
    { // limites
        return false;
    }
    else
    {
        if (lab[linha][coluna] == '#' || lab[linha][coluna] == 'x')
        { // parede ou já visitado
            return false;
        }
        else if (lab[linha][coluna] == 'S')
        {
            return true;
        }
    }

    if (lab[linha][coluna] == '.' || lab[linha][coluna] == 'E')
    {
        char aux = lab[linha][coluna]; //guarda valor original
        if (lab[linha][coluna] != 'E')
            lab[linha][coluna] = 'x';

        // cima, baixo, esquerda, direita
        if (caminho(lab, linha - 1, coluna))
            return true;
        if (caminho(lab, linha + 1, coluna))
            return true;
        if (caminho(lab, linha, coluna - 1))
            return true;
        if (caminho(lab, linha, coluna + 1))
            return true;

        lab[linha][coluna] = aux;

    }

    return false;
}

void imprimirLabirinto(char lab[TAM][TAM])
{
    int i, j;

    for (i = 0; i < TAM; i++)
    {
        for (j = 0; j < TAM; j++)
        {
            printf("%c ", lab[i][j]);
        }
        printf("\n");
    }

    printf("\n");
}

int main()
{
    char labirinto[TAM][TAM] = {
        {'#', '#', '#', '.', '#', '.', '#', '#', '#', '#'},
        {'E', '.', '.', '#', '.', '.', '.', '#', '.', '#'},
        {'#', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
        {'#', '.', '.', '.', '.', '#', '.', '.', '.', '#'},
        {'#', '.', '#', '#', '#', '#', '#', '#', '.', '#'},
        {'.', '.', '#', '.', '.', '.', '#', '.', '.', '#'},
        {'#', '.', '#', '#', '#', '.', '#', '#', '.', '#'},
        {'#', '.', '.', '.', '.', '.', '.', '#', '.', '.'},
        {'#', '#', '#', '#', '#', '#', '.', '.', '.', 'S'},
        {'#', '#', '#', '#', '#', '#', '.', '#', '#', '#'}};

    int linha_E, coluna_E;

    encontrar_E(labirinto, &linha_E, &coluna_E);
    
    printf("___ Original ___\n");
    imprimirLabirinto(labirinto);

    if (caminho(labirinto, linha_E, coluna_E))
    {
        printf("___ Solucao Recursiva ___\n");
        imprimirLabirinto(labirinto);
    }

    // printf("___ Solucao Interativa ___\n");
    // pathfinder_Iterative(labirinto, linha_E, coluna_E);
    // imprimirLabirinto(labirinto);

    return 0;
}