Caminhos em grade com obstáculos: contagem de trajetos para a direita e para cima
Desenhe a grade com casas livres e bloqueadas: veja o número de caminhos do canto inferior esquerdo ao superior direito e quantos chegam a cada casa.
- Roda no seu navegador
Resultado
O resultado aparece aqui.
Como a contagem é feita
Desenhe a grade com uma linha de texto por fileira: ponto (.) para a casa livre e cerquilha (#) para a casa bloqueada. O caminho sai do canto inferior esquerdo e chega ao canto superior direito, andando só para a direita ou para cima e sem pisar em casa bloqueada. A ferramenta conta todos os caminhos possíveis e mostra, em cada casa, quantos caminhos chegam até ela.
caminhos até uma casa = caminhos até a casa de baixo + caminhos até a casa da esquerda (0 se a casa é bloqueada); sem bloqueios, C(linhas + colunas − 2, linhas − 1)
Exemplo: grade 3 por 3
Em uma grade 3 por 3 com a casa do meio bloqueada, restam 2 caminhos (contra 6 sem bloqueios): um por cima e outro por baixo. A tabela mostra os caminhos que chegam a cada casa.
| Coluna 1 | Coluna 2 | Coluna 3 |
|---|---|---|
| 1 | 1 | 2 |
| 1 | # | 1 |
| 1 | 1 | 1 |
Exemplo: grade 8 por 8 com sete bloqueios
Em uma grade 8 por 8 com sete casas bloqueadas há 1492 caminhos, contra 3432 sem bloqueios.
Limites
- A grade vai de 1 a 20 linhas e de 1 a 20 colunas, todas as linhas do mesmo tamanho; sem bloqueios, o total máximo é C(38, 19) = 35.345.263.800.
- Se o canto inicial ou o final estiver bloqueado, a ferramenta avisa e o total é zero.
- Só há movimentos para a direita e para cima; caminhos com outros movimentos exigem outro cálculo.
Perguntas frequentes
Como contar caminhos em uma grade com obstáculos?
Desenhe a grade com . e #: no exemplo 3 por 3 com o centro bloqueado, são 2 caminhos.
Quantos caminhos existem em uma grade sem obstáculos?
São C(linhas + colunas − 2, linhas − 1) caminhos: 3432 em uma grade 8 por 8.
Como contar trajetos canto a canto sem caminho possível?
A ferramenta avisa quando nenhum caminho chega ao canto final ou quando um dos cantos está bloqueado; remova algum bloqueio e conte de novo.