Padrão 4: Backtracking em grid
Backtracking é o DFS com uma virada: você marca uma célula ao entrar num caminho e a desmarca ao sair, liberando-a para outras tentativas. É como explorar um labirinto desenrolando um fio e recolhendo-o quando volta.
Tente primeiro: Word Search
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Dado um grid de letras board e uma word, retorne true se a palavra pode ser formada por letras adjacentes (horizontal/vertical), sem reusar a mesma célula.
Exemplo: board [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word "ABCCED" → true.
Tentou? O difícil aqui não é achar a primeira letra — é não reusar a mesma célula no caminho, e conseguir tentar outro caminho quando um falha. A teoria abaixo mostra a peça que faltava: desfazer a marca ao voltar.
A teoria: marcar, explorar, desmarcar
No flood fill (aula 4), uma célula visitada ficava marcada para sempre — queríamos cobrir a região uma vez. No backtracking é diferente: queremos achar um caminho específico, e uma célula que não serviu para este caminho pode servir para outro. Por isso, a marca é temporária:
dfs(r, c, i): # tenta casar word[i] em (r,c)
se i == len(word) → achou tudo! return True
se fora do grid
ou grid[r][c] != word[i] → return False
se (r,c) já está no caminho → return False
marca (r,c) no caminho # ENTRA
tenta os 4 vizinhos para word[i+1] (se algum der True, propaga)
desmarca (r,c) do caminho # SAI (backtrack!)
return (se algum vizinho deu certo)
A linha "desmarca" é o coração do backtracking. Sem ela, uma tentativa falha bloquearia células para sempre e caminhos válidos seriam perdidos. Veja o caminho (verde) crescer ao avançar e encolher quando o DFS volta — é o backtrack acontecendo diante dos seus olhos:
(No visualizador, a palavra é ABFD: acompanhe o caminho tentar uma direção,
falhar, recuar e tentar outra, até montar a palavra.)
Por que a complexidade é exponencial no pior caso?
De cada célula, o DFS pode seguir até ~4 direções, e a busca tenta começar de
cada uma das m·n células. No pior caso, isso dá algo como O(m·n·4ᴸ),
onde L é o tamanho da palavra (de cada célula partem ~3 novas direções, L
vezes). É exponencial em L — e tudo bem: backtracking explora um espaço de
busca que pode ser grande, mas a poda (parar assim que grid[r][c] != word[i])
corta a imensa maioria dos ramos cedo. O espaço é O(L) (profundidade da
recursão / tamanho do caminho).
DFS vs. backtracking: são primos. No flood fill, a marca é permanente (cobrir uma região). No backtracking, a marca é desfeita (explorar caminhos alternativos). Reconhecer qual dos dois o problema pede é meio caminho.
Onde backtracking aparece
Word Search, gerar permutações/combinações, Sudoku, N-Queens, labirintos com "todos os caminhos". O esqueleto é sempre o mesmo: escolher → explorar → desfazer a escolha. Você vai reencontrá-lo fora dos grids também — é um dos padrões mais transferíveis do curso.
🧠 Quiz de fixação
0/41. Qual a diferença essencial entre o DFS do flood fill (aula 4) e o backtracking?
2. Por que a linha 'desmarca a célula' é indispensável no word search?
3. O que permite ao backtracking, apesar da complexidade exponencial no pior caso, ser viável na prática?
4. Qual é o esqueleto geral de qualquer backtracking?
Resumo
- Backtracking = DFS com marca temporária: marca ao entrar, desmarca ao sair.
- Word Search: casa
word[i]na célula, tenta os vizinhos paraword[i+1], desfaz ao falhar. - Pior caso exponencial em L, mas a poda o torna viável; espaço O(L).
- Esqueleto universal: escolher → explorar → desfazer.
Próxima aula: quando a pergunta é "o caminho mais curto" — BFS.