Este artigo demonstra como utilizar a estrutura de dados fila (queue) e o algoritmo de Busca em Largura (BFS) em C++ para determinar o caminho mais curto dentro de um labirinto representado por uma grade.

Conceitos Fundamentais

Uma fila é uma coleção de elementos que segue o princípio FIFO (First-In, First-Out). A inserção ocorre em uma extremidade (traseira) e a remoção na outra (frontal). Esta estrutura é ideal para modelar processos que requerem a ordenação pela ordem de chegada, como a exploração por camadas realizada pelo BFS.

O algoritmo BFS explora todos os vizinhos de um nó antes de avançar para os vizinhos dos vizinhso. Em um grafo ou grade ponderada uniformemente (como um labirinto sem custos variados), o BFS garante a descoberta do caminho de menor número de arestas (passos) entre dois nós.

Definindo a Estrutura do Problema

Para resolver o labirinto, precisamos definir alguns componentes-chave:

• Mapa do Labirinto: Uma matriz 2D indicando células livres (0) e obstáculos (1).
• Fila para BFS: Para gerenciar os nós a serem explorados.
• Matriz de Visitados: Para evitar a reexploração de nós.
• Matriz de Pais: Para rastrear o caminho percorrido e permitir a reconstrução da rota.
• Matriz de Direções: Para definir os movimentos possíveis (cima, baixo, esquerda, direita).

Incluímos as bibliotecas necessárias:

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

Definimos uma estrutura para representar coordenadas e as variáveis globais que descrevem o labirinto:

struct Coordenada {
    int lin, col;
    Coordenada(int l = 0, int c = 0) : lin(l), col(c) {}
};

const int LINHAS = 10;
const int COLUNAS = 10;
int labirinto[LINHAS][COLUNAS] = {
    {0, 0, 0, 0, 1, 0, 1, 0, 1, 0},
    {0, 1, 0, 0, 0, 1, 0, 0, 0, 0},
    {0, 0, 0, 1, 0, 0, 1, 1, 0, 0},
    {0, 1, 0, 0, 0, 1, 0, 0, 0, 0},
    {0, 1, 0, 1, 0, 0, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
    {1, 1, 1, 1, 1, 1, 1, 1, 0, 1},
    {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
    {1, 1, 1, 1, 0, 0, 0, 1, 1, 1},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};

Coordenada origem(0, 0);
Coordenada destino(LINHAS - 1, COLUNAS - 1);
bool visitado[LINHAS][COLUNAS] = {false};
Coordenada pai[LINHAS][COLUNAS];
const int movimentos[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

Implementação do Algoritmo BFS

A função encontrarCaminho encapsula a lógica do BFS. Ela retorna um vetor com as coordenadas do caminho mais curto da origem ao destino, ou um vetor vazio se não houver caminho.

vector<Coordenada> encontrarCaminho() {
    queue<Coordenada> fila;
    fila.push(origem);
    visitado[origem.lin][origem.col] = true;

    while (!fila.empty()) {
        Coordenada atual = fila.front();
        fila.pop();

        // Verifica se chegamos ao destino
        if (atual.lin == destino.lin && atual.col == destino.col) {
            vector<Coordenada> caminho;
            for (Coordenada c = destino; !(c.lin == origem.lin && c.col == origem.col); c = pai[c.lin][c.col]) {
                caminho.push_back(c);
            }
            caminho.push_back(origem);
            reverse(caminho.begin(), caminho.end());
            return caminho;
        }

        // Explora os vizinhos
        for (int i = 0; i < 4; ++i) {
            int nova_lin = atual.lin + movimentos[i][0];
            int nova_col = atual.col + movimentos[i][1];

            // Verifica limites, obstáculos e se já foi visitado
            if (nova_lin >= 0 && nova_lin < LINHAS &&
                nova_col >= 0 && nova_col < COLUNAS &&
                labirinto[nova_lin][nova_col] == 0 &&
                !visitado[nova_lin][nova_col]) {
                
                visitado[nova_lin][nova_col] = true;
                pai[nova_lin][nova_col] = atual;
                fila.push(Coordenada(nova_lin, nova_col));
            }
        }
    }
    return vector<Coordenada>(); // Caminho não encontrado
}

Execução e Saída do Programa

No main, invocamos a função e formatamos a saída para exibir o caminho encontrado, se existir.

int main() {
    vector<Coordenada> caminho = encontrarCaminho();

    if (caminho.empty()) {
        cout << "Não existe caminho até o destino." << endl;
    } else {
        cout << "Comprimento do caminho mais curto: " << caminho.size() - 1 << endl;
        cout << "\nPasso a passo:" << endl;
        for (size_t i = 0; i < caminho.size(); ++i) {
            cout << "(" << caminho[i].lin << ", " << caminho[i].col << ")";
            if (i < caminho.size() - 1) {
                cout << " -> ";
                if ((i + 1) % 5 == 0) cout << endl;
            }
        }
        cout << endl;
    }
    return 0;
}

O algoritmo garante a otimalidade porque explora o labirinto camada por camada. A primeira vez que o destino é removido da fila, o caminho até ele necessariamente é o de menor comprimento. A matriz pai permite reconstruir essa rota ótima retrocedendo do destino até a origem.