Como calcular o número de caminhos mais curtos sem enlouquecer com fatoriais
Você já precisou contar quantos caminhos existem num grid de rua pra rua, indo só pra direita e pra cima, e terminou fazendo contas de cabeça porque a calculadora não ajudava? O diagrama das diagonais resolve isso num piscar de olhos. Não é mágica, é combinatorics aplicada de um jeito que a maioria dos livros didáticos explica de forma confusa. O método funciona assim: você monta uma tabela onde cada célula representa um ponto do grid, e preenche usando adição simples. O segredo é que cada posição herda a soma dos valores das células imediatamente acima e à esquerda. É basicamente o triângulo de Pascal disfarçado de grade.
Montando o diagrama das diagonais na prática
Comece desenhando sua grade. Se você quer ir do canto inferior esquerdo até o superior direito num grid de 5 por 5, você desenha 5 colunas e 5 linhas. Preencha a célula de origem com 1. Daí, para cada célula seguinte, some o valor de cima com o valor da esquerda. Quando a célula está na borda superior ou esquerda, ela só tem um vizinho contribuinte, então copia o valor daquele vizinho. O que muitos não entendem na hora é que as diagonais da tabela formada correspondem aos coeficientes binomiais. A soma ao longo de uma diagonal específica dá o número de caminhos até qualquer ponto naquela "camada" do grid. Isso é útil porque permite generalizar sem refazer toda a tabela.
Pra quem programa isso, a implementação é trivial. Um loop duplo com uma condição de borda resolve em menos de 10 linhas de código. Em Python puro: grid = [[0] * n para _ em range(n)]
grid[0][0] = 1
para i de 0 a n-1:
para j de 0 a n-1:
se i > 0: grid[i][j] += grid[i-1][j]
se j > 0: grid[i][j] += grid[i][j-1]
O resultado final está na célula [n-1][n-1]. Pronto.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Onde esse método realmente brilha
A vantagem real do diagrama das diagonais aparece quando você precisa responder múltiplas consultas sobre o mesmo grid. Se você tem uma estrutura urbana e quer saber caminhos pra vários destinos diferentes, monta a tabela uma vez e lê os valores de qualquer célula. Sem essa abordagem, você teria que recalcular tudo do zero pra cada destino, o que escala mal rápido demais. Em termos de performance, um grid 100x100 processado dessa forma leva menos de 0,01 segundos. Uma abordagem recursiva ingênua levanta dias no mesmo problema. A diferença não é marginal, é absoluta.
Um caso que eu vi dar errado
Já me deparei com alguém usando o diagrama das diagonais num grid que tinha obstáculos — blocos que não podiam ser atravessados. O método padrão simplesmente explode nesse cenário porque ele assume que todas as células são acessíveis. A pessoa ficou horas tentando ajustar manualmente e não chegava a lugar nenhum. A solução que eu uso é simples: quando a célula é um obstáculo, você zera o valor dela ou simplesmente pula o processamento daquela posição. Os vizinhos downstream naturalmente não somam nada daquela célula obstruída. Funciona perfeitamente e leva uns 30 segundos a mais na implementação. Só não funciona se os obstáculos criarem rotas que dependem de retroalimentação — aí você precisa de um algoritmo de grafos mesmo, tipo Dijkstra ou BFS.
Limitações que ninguém conta
O diagrama das diagonais tem um limite prático claro: memória. Grids muito grandes (digamos, acima de 1000x1000) começam a consumir memória considerável só pra guardar a tabela. Se você precisa lidar com grids desse porte, é melhor usar a fórmula combinatória direta — C(n+k, k) — que exige O(1) de memória extra. Outro ponto: o método só funciona pra movimento restrito a duas direções (direita e cima, ou equivalente). Se você permite movimento em diagonais, em qualquer direção, ou tem pesos diferentes por célula, o diagrama perde a utilidade. Nesses casos, algoritmos de grafos são a única opção sensata.
Tem ainda o problema de números gigantes. Em grids 50x50, o resultado já passa de 10^29. Muita linguagem precisa de bibliotecas deBigInt pro tratamento correto. Python resolve isso nativamente, mas em C ou Java você vai precisar de classes específicas. Isso não quebra o método, só adiciona uma camada de complexidade que vale a pena antecipar.
Download do template
Se você quer um arquivo pronto pra usar, monte sua própria planilha. A lógica é tão simples que não compensa depender de ferramenta pronta — além disso, planilhas travam com grades grandes. Um script Python de 15 linhas faz o trabalho completo e gera um CSV com todos os resultados. Se quiser, posso deixar o código acima como referência pra você adaptar.
