Caminhos numa grade

Um labirinto, uma planta de prédio ou um mapa de jogo podem ser guardados como uma grade: um arquivo de texto em que cada caractere é uma casa (# parede, . chão). Andar de casa em casa (cima, baixo, esquerda, direita) e achar o caminho mais curto entre dois pontos é um problema clássico, e a solução padrão é a busca em largura (BFS, de breadth-first search).

A ideia: visitar as casas em ondas. Primeiro todas a 1 passo da entrada, depois todas a 2 passos, depois a 3, como uma pedra jogada num açude. Como cada casa é visitada pela primeira vez pela onda mais curta que chega nela, a primeira vez que a onda alcança a saída já é pelo caminho mais curto. Para recuperar o caminho, cada casa anota de onde veio; no fim, basta voltar da saída até a entrada seguindo essas anotações.

Exemplo pequeno:

S.#
.##
..E

Do S (canto de cima à esquerda), a onda 1 alcança a casa à direita e a de baixo; a onda 2 alcança a casa no canto de baixo à esquerda; a onda 3, a do meio embaixo; a onda 4 chega no E. O caminho mais curto tem 4 passos: baixo, baixo, direita, direita.

Em Python, a fila é uma collections.deque (tira do começo, põe no fim) e as anotações ficam num dicionário:

from collections import deque
veio_de, fila = {S: None}, deque([S])
while fila:
    x, y = fila.popleft()
    for vizinho in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
        nx, ny = vizinho
        if grade[ny][nx] != "#" and vizinho not in veio_de:
            veio_de[vizinho] = (x, y)
            fila.append(vizinho)

Seguir a parede com a mão, ou o primeiro caminho que aparece, chega na saída, mas não necessariamente pelo caminho mais curto quando o labirinto tem voltas.

Isso importa porque a mesma busca acha a rota com menos saltos numa rede, o caminho de ataque mais curto num mapa de permissões e a distância entre quaisquer dois pontos de um grafo.