Aula prática · Busca em largura

O cavalo quer o menor caminho.

Cada casa do tabuleiro vira um vértice. Cada movimento possível do cavalo vira uma aresta. A BFS explora o tabuleiro por distâncias crescentes até encontrar o destino.

BFS Fila Menor caminho Tabuleiro 8×8 C++17
01

Contexto do problema

Dados dois quadrados do tabuleiro, precisamos descobrir o menor número de movimentos do cavalo necessário para sair da origem e alcançar o destino.

Entrada

Dois quadrados

Exemplo: e2 e4. O primeiro é a origem e o segundo é o destino.

Objetivo

Menor quantidade

Não basta encontrar um caminho. Precisamos garantir que seja o caminho com menos movimentos.

Saída

Número de movimentos

Imprimimos a frase pedida pelo problema com a distância encontrada.

Mesmo que origem e destino sejam iguais, o algoritmo funciona: a resposta é 0. Isso aparece no exemplo f6 f6.
02

O tabuleiro é um grafo

Para resolver com grafos, basta reinterpretar o tabuleiro.

Vértices

64 casas

Cada quadrado do tabuleiro representa um vértice.

a1, a2, ..., h8
Arestas

Movimentos válidos

Existe uma aresta entre duas casas quando o cavalo pode ir de uma para a outra em um único movimento.

Casa do tabuleiro
→
Vértice
→
Movimento do cavalo
→
Aresta
Como cada movimento custa exatamente 1, o grafo é não ponderado para este problema.
03

Os 8 movimentos possíveis do cavalo

O cavalo sempre faz um deslocamento em “L”: duas casas em um eixo e uma no outro.

•
•
•
•
♞
•
•
•
•
#include <array>
#include <utility>

const std::array<std::pair<int, int>, 8> movimentos{{
    { 2,  1}, { 2, -1},
    {-2,  1}, {-2, -1},
    { 1,  2}, { 1, -2},
    {-1,  2}, {-1, -2}
}};
Alguns desses movimentos podem cair fora do tabuleiro. Por isso sempre testamos: 0 <= nx < 8 e 0 <= ny < 8.
04

Por que BFS?

A BFS percorre o grafo por camadas de distância.

distância 0
→
distância 1
→
distância 2
→
distância 3...
1

Começa na origem

Origem entra na fila com distância 0.

2

Explora vizinhos

Todos os movimentos possíveis recebem distância +1.

3

Primeiro encontro

Quando o destino é retirado da fila, aquela distância é mínima.

A BFS garante o menor número de arestas em um grafo não ponderado. Aqui, uma aresta equivale a um movimento do cavalo.
05

BFS animada — e2 até e4

Este exemplo precisa de 2 movimentos. A animação mostra a expansão por camadas.

O mesmo exemplo como grafo

Cada bolinha é uma casa do tabuleiro. Cada linha é um movimento válido do cavalo que a BFS está considerando neste trecho.

Execução passo 0
Clique em “Próximo” ou “Executar”.
Fila
Posição atual —
Distância atual 0
A BFS não “adivinha” o caminho. Ela explora primeiro todas as casas a 1 movimento. Só depois começa a processar as casas a 2 movimentos.
06

Algoritmo em C++17

#include <array>
#include <queue>
#include <string>
#include <tuple>
#include <utility>

int bfs(const std::string& origem, const std::string& destino) {
    int x = origem[1] - '1';
    int y = origem[0] - 'a';
    int alvo_x = destino[1] - '1';
    int alvo_y = destino[0] - 'a';

    std::array<std::array<bool, 8>, 8> visitado{};
    std::queue<std::tuple<int, int, int>> fila;

    visitado[x][y] = true;
    fila.push({x, y, 0});

    const std::array<std::pair<int, int>, 8> movimentos{{
        {2,1}, {2,-1}, {-2,1}, {-2,-1},
        {1,2}, {1,-2}, {-1,2}, {-1,-2}
    }};

    while (!fila.empty()) {
        auto [atual_x, atual_y, distancia] = fila.front();
        fila.pop();

        if (atual_x == alvo_x && atual_y == alvo_y)
            return distancia;

        for (auto [dx, dy] : movimentos) {
            int nx = atual_x + dx;
            int ny = atual_y + dy;

            if (nx >= 0 && nx < 8 &&
                ny >= 0 && ny < 8 &&
                !visitado[nx][ny]) {
                visitado[nx][ny] = true;
                fila.push({nx, ny, distancia + 1});
            }
        }
    }

    return -1;
}
std::queue<Estado> fila;
BFS precisa de uma fila. Entramos no final e retiramos da frente.
auto [linha, coluna, distancia] = fila.front(); fila.pop();
Processamos o elemento mais antigo. Isso preserva a ordem por camadas.
fila.push({nx, ny, distancia + 1});
Todo vizinho está uma aresta mais distante. Portanto recebe distância +1.
visitado[nx][ny] = true;
Marcamos ao colocar na fila. Assim a mesma casa não entra várias vezes.
07

Entrada e saída do exemplo

Exemplo de entrada

e2 e4 a1 b2 b2 c3 a1 h8 a1 h7 h8 a1 b1 c3 f6 f6

Exemplo de saída

To get from e2 to e4 takes 2 knight moves. To get from a1 to b2 takes 4 knight moves. To get from b2 to c3 takes 2 knight moves. To get from a1 to h8 takes 6 knight moves. To get from a1 to h7 takes 5 knight moves. To get from h8 to a1 takes 6 knight moves. To get from b1 to c3 takes 1 knight moves. To get from f6 to f6 takes 0 knight moves.
b1 → c3

1 movimento

c3 é diretamente alcançável pelo cavalo a partir de b1.

a1 → h8

6 movimentos

A BFS expande várias camadas até alcançar o destino.

f6 → f6

0 movimentos

A origem já é o destino; a primeira posição retirada da fila resolve o caso.

08

O que o aluno precisa guardar

Modelagem

Casa = vértice. Movimento válido = aresta.

BFS

Explora por níveis usando uma fila.

Menor caminho

Em grafo não ponderado, a primeira distância encontrada pela BFS é mínima.

Elemento do problemaInterpretação em grafos
Casa do tabuleiroVértice
Movimento do cavaloAresta
Quantidade de movimentosDistância
Estrutura auxiliarFila
AlgoritmoBFS
Frase para memorizar: “Se todas as arestas custam 1 e quero a menor quantidade de passos, pense em BFS.”