A resolução de labirintos é um problema clássico de computação que pode ser abordado eficientemente através do algoritmo de Busca em Profundidade (Depth-First Search - DFS). Utilizando uma estrutura de dados do tipo Pilha (Stack), podemos explorar caminhos de forma recursiva ou iterativa, permitindo o retrocesso (backtracking) quando encontramos um beco sem saída.

Lógica do Algoritmo

O funcionamento baseia-se em partir de uma coordenada inicial (entrada) e tentar avançar para células adjacentes sgeuindo uma ordem de prioridade (por exemplo: Direita, Baixo, Esquerda, Cima). O fluxo segue os seguintes passos:

1. Empilha a posição inicial.
2. Enquanto a pilha não estiver vazia:
   • Obtém a posição atual do topo da pilha.
   • Verifica se a posição atual é o destino. Se sim, o caminho foi encontrado.
   • Marca a posição atual como visitada para evitar loops.
   • Tenta encontrar um vizinho válido (sem parede e não visitado).
   • Se encontrar, empilha o vizinho e continua.
   • Se não houver vizinhos disponíveis, desempilha a posição atual (backtracking).

Implementação da Estrutura de Dados

Primeiro, definimos a estrutura básica para as coordenadas e para a pilha que armazenará o caminho percorrido.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int x;
    int y;
} Coordenada;

typedef struct {
    int topo;
    int capacidade;
    Coordenada* itens;
} PilhaBusca;

PilhaBusca* inicializarPilha(int tamanho) {
    PilhaBusca* p = (PilhaBusca*)malloc(sizeof(PilhaBusca));
    p->capacidade = tamanho;
    p->topo = -1;
    p->itens = (Coordenada*)malloc(sizeof(Coordenada) * tamanho);
    return p;
}

int estaVazia(PilhaBusca* p) {
    return p->topo == -1;
}

void empilhar(PilhaBusca* p, Coordenada c) {
    p->itens[++(p->topo)] = c;
}

Coordenada desempilhar(PilhaBusca* p) {
    return p->itens[(p->topo)--];
}

Coordenada topo(PilhaBusca* p) {
    return p->itens[p->topo];
}

Resolução do Labirinto com DFS

A função principal de processamento recebe a matriz do labirinto, as dimensões e os pontos de controle. Note que as posições visitadas são marcadas na própria matriz para otimização de memória.

void resolverLabirinto(int** mapa, int linhas, int colunas, Coordenada inicio, Coordenada fim) {
    PilhaBusca* caminho = inicializarPilha(linhas * colunas);
    empilhar(caminho, inicio);

    int resolvido = 0;

    while (!estaVazia(caminho)) {
        Coordenada atual = topo(caminho);

        if (atual.x == fim.x && atual.y == fim.y) {
            resolvido = 1;
            break;
        }

        // Marcar como visitado (valor 0)
        mapa[atual.y][atual.x] = 0;

        // Tentar Direita
        if (atual.x + 1 < colunas && mapa[atual.y][atual.x + 1] == 1) {
            Coordenada proximo = {atual.x + 1, atual.y};
            empilhar(caminho, proximo);
        }
        // Tentar Baixo
        else if (atual.y + 1 < linhas && mapa[atual.y + 1][atual.x] == 1) {
            Coordenada proximo = {atual.x, atual.y + 1};
            empilhar(caminho, proximo);
        }
        // Tentar Esquerda
        else if (atual.x - 1 >= 0 && mapa[atual.y][atual.x - 1] == 1) {
            Coordenada proximo = {atual.x - 1, atual.y};
            empilhar(caminho, proximo);
        }
        // Tentar Cima
        else if (atual.y - 1 >= 0 && mapa[atual.y - 1][atual.x] == 1) {
            Coordenada proximo = {atual.x, atual.y - 1};
            empilhar(caminho, proximo);
        }
        else {
            desempilhar(caminho);
        }
    }

    if (resolvido) {
        printf("Caminho encontrado. Coordenadas (Y, X):\n");
        while (!estaVazia(caminho)) {
            Coordenada p = desempilhar(caminho);
            printf("[%d, %d] ", p.y, p.x);
        }
        printf("\n");
    } else {
        printf("Não existe saída possível para este labirinto.\n");
    }

    free(caminho->itens);
    free(caminho);
}

Análise de Complexidade

O algoritmo de busca em profundidade aplicado a matrizes possui uma complexidade de tempo de O(V + E), onde V representa o número de células (vértices) e E o número de conexões possíveis entre elas (arestas). No contexto de uma grade, isso simplifica para O(N * M), sendo N e M as dimensões da matriz. O espaço em memória também é O(N * M) no pior cenário, devido ao armazenamento da pilha.

Embora a DFS encontre uma solução de forma eficaz, ela não garante o caminho mais curto. Para encontrar a menor distância em um labirinto sem pesos, algoritmos como o BFS (Busca em Largura) são mais indicados.