Em Um Tabuleiro De 1x100 Quadrados

Como lidar com problemas em um tabuleiro de 1x100 quadrados

O tabuleiro 1x100 aparece com frequência em problemas de combinatorics, programação dinâmica e teoria dos grafos. A maioria das pessoas subestima o que acontece quando o tabuleiro cresce beyond o óbvio. Vou explicar como resolver esses problemas na prática, com os erros que eu cometi e as soluções que realmente funcionam.

Entendendo em um tabuleiro de 1x100 quadrados

Antes de falar de métodos, é preciso entender a estrutura básica. Um tabuleiro 1x100 é uma fileira de 100 casas, geralmente numeradas de 1 a 100. O que você faz com ele depende do problema: contar caminhos, colocar peças (dominós, trocamos), ou calcular probabilidades de movimento. A complicação não está na configuração em si, mas nas regras que você aplica sobre ela. Um exemplo clássico é o problema de contar quantas formas existem para chegar da casa 1 à casa 100, onde você pode avançar 1 ou 2 casas por vez. A respostaSegue a sequência de Fibonacci, sim, mas só porque funciona para tabuleiros pequenos. Quando o número de casas sobe para 100, a abordagem recursiva ingênua travacompletamente. Os valores crescem exponencialmente e você acaba lidando com números enormes rapidamente. O número de caminhos possíveis para um tabuleiro 1x100 com passos de 1 ou 2 casas é F(100), que é aproximadamente 3,54 × 10^20. Isso não cabe em um inteiro de 64 bits. Você precisa de aritmética de bigint ou uma linguagem como Python que lida com isso automaticamente.

Aqui vai algo que pouca gente menciona: muitas vezes o problema não pede o valor exato, mas sim o resultado módulo algum número. Se for o caso, você pode aplicar a propriedade de Pisano — a sequência de Fibonacci é periódica módulo qualquer n. Para módulo 10^9+7, por exemplo, o período de Pisano é 1.500.000.006. Isso significa que F(n) mod M repete a cada ~1,5 bilhão de termos. Útil? Depende. Para n=100 não ajuda muito, mas para problemas competitivos com n na casa dos 10^18, essa informação é o que separa uma solução que roda em milissegundos de uma que leva horas.

Problema prático: tabuleiro com casas bloqueadas

Eu já enfrentei um cenário onde partes do tabuleiro 1x100 estavam bloqueadas e você precisava contar caminhos válidos da posição inicial à final, sem passar por casas proibidas. A solução ingênua seria backtracking, mas com 100 casas e ramificações exponenciais, isso simplesmente não escala. A abordagem correta usa programação dinâmica com memoização. O truque é definir dp[i] como o número de caminhos válidos para chegar à casa i. A transição é simples: dp[i] = dp[i-1] + dp[i-2], desde que a casa i não esteja bloqueada. Se estiver bloqueada, dp[i] = 0. Você itera de 1 a 100, acumulando os valores. Tempo: O(n). Espaço: O(n) — ou O(1) se você otimizar guardando apenas os dois últimos valores.

O problema que eu encontrei na prática foi com um conjunto de bloqueios que criavam "ilhas" isoladas. Ou seja, certas regiões do tabuleiro ficavam completamente inacessíveis a partir do início, mas o algoritmo DP padrão não detectava isso de forma explícita. Ele simplesmente propagava zeros, o que está correto matematicamente, mas pode mascarar erros de implementação se você não validar os casos limite. Minha solução foi adicionar uma verificação pós-computação: se dp[100] == 0, fazer uma busca BFS/DFS para confirmar que realmente não há caminho, e não apenas que a DP encontrou um caminho inválido devido a um bug.

Pegadinhas comuns e como evitá-las

Primeiro: confundir a orientação do tabuleiro. Um tabuleiro 1x100 não é o mesmo que 100x1. Se o problema envolve movimento nas duas direções (esquerda e direita), você precisa tratar isso explicitamente. A maioria dos problemas clássicos restringe o movimento a apenas uma direção, o que simplifica tudo. Segundo: esquecernúmeros grandes. Mesmo que a lógica esteja perfeita, se você usar inteiros de 32 bits, vai estourar em n maior que 93 para Fibonacci. Use tipos BigInteger ou langagens que lidam com isso nativamente.

Terceiro: sobresimplificar quando o problema pede algo mais complexo, como contar caminhos com um número específico de pares de passos consecutivos. Nesse caso, você precisa expandir o estado da DP para incluir informações adicionais, como o último passo dado. O estado vira dp[i][ultimo_passo], e a complexidade sobe, mas ainda é manejável.

Código prático

Aqui está uma implementação direta em Python para o caso básico (passos de 1 ou 2, sem bloqueios):

def caminhar_1x100(n=100):
    if n = 0: return 0
    if n == 1: return 1
    if n == 2: return 2
    
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

Para o caso com casas bloqueadas, você adiciona uma lista de posições proibidas e zera o dp correspondente. O resto permanece igual.

Quando esse modelo falha

O tabuleiro 1x100 com DP linear é uma ferramenta poderosa, mas tem limites claros. Se as regras de movimento permitirem saltos de qualquer tamanho (não apenas 1 ou 2), a recorrência muda e pode exigir otimizações como matrizes de transição ou multiplicação de matrizes para grandes n. Se houver dependências entre casas não adjacentes — por exemplo, uma casa bloqueia outra a 5 posições de distância — a DP linear simples não basta e você precisa de uma estrutura de grafo mais elaborada. Também vale lembrar que, embora o tabuleiro seja 1x100, a complexidade real do problema pode ser muito maior. O tamanho do tabuleiro é apenas o tamanho do input. O que importa são as regras de transição. Já vi problemas aparentemente simples em tabuleiros 1x100 que se revelaram NP-difíceis quando as regras de movimento incluem restrições de paridade ou condições globais sobre o conjunto de casas visitadas.

Na prática, a melhor abordagem é sempre começar com uma versão simplificada do problema, testar com tabuleiros pequenos (1x10, 1x20) para validar a lógica, e só então escalar para 1x100. Isso evita surpresas com bugs que só aparecem em tamanhos maiores.