Em uma grade retangular composta por n linhas e m colunas de quadrados unitários, deseja-se contar duas coisas distintas:

1. Todos os quadrados cujos lados são paralelos às linhas da grade, com comprimentos de lado variando de 1 até o menor valor entre n e m.
2. Todos os retângulos não quadrados, ou seja, retângulos onde o comprimento é diferente da largura.

Para efeitos de contagem, um quadrado é considerado um caso especial de retângulo, mas aqui os dois são contados separadamente.

Contagem do Total de Retângulos

Para definir um retângulo qualquer na grade, precisamos selecionar duas linhas horizontais como bordas superior e inferior, e duas linhas verticais como bordas esquerda e direita. Existem n+1 linhas horizontais e m+1 linhas verticais.

• O número de maneiras de escolher duas linhas horizontais distintas é a combinação C(n+1, 2) = n(n+1)/2.
• O número de maneiras de escolher duas linhas verticais distintas é C(m+1, 2) = m(m+1)/2.

Portanto, o número total de retângulos (incluindo quadrados) é:

T = (n * (n + 1) / 2) * (m * (m + 1) / 2)

Contagem de Quadrados: Abordagem Iterativa

Seja k o comprimento do lado de um quadrado (1 ≤ k ≤ min(n, m)). Para que um quadrado de lado k caiba na grade, sua posição superior esquerda pode variar horizontalmente em (n - k + 1) posições e verticalmente em (m - k + 1) posições. O número total de quadrados de lado k é (n - k + 1) * (m - k + 1). Somando para todos os valores possíveis de k:

S = Σ (de k=1 até min(n,m)) [(n - k + 1) * (m - k + 1)]

Esta abordagem tem complexidade O(min(n,m)), sendo eficiente para valores moderados.

Contagem de Quadrados: Fórmula Fechada Otimizada

É possível derivar uma expressão matemática direta para S. Defina a = min(n, m) e b = max(n, m). Também defina d = b - a. Reorganizando a soma, obtemos:

S = Σ (de x=1 até a) [x * (d + x)]

Aplicando as fórmulas de soma Σx = a(a+1)/2 e Σx² = a(a+1)(2a+1)/6, chegamos a:

S = d * [a(a+1)/2] + [a(a+1)(2a+1)/6]
S = a(a+1)(3b - a + 1) / 6

Esta fórmula calcula o resultado em tempo constante O(1).

Exemplo de Verificação

Para n=2, m=3: a=2, b=3. Aplicando a fórmula:

S = 2 * 3 * (3*3 - 2 + 1) / 6
  = 6 * (9 - 2 + 1) / 6
  = 6 * 8 / 6
  = 8

Que corresponde à contagem manual.

Cálculo do Número de Retângulos Não Quadrados

Uma vez que temos o total de retângulos T e o total de quadrados S, o número de retângulos que não são quadrados é simplesmente:

Retângulos Não Quadrados = T - S

Implementação em Código

Versão Iterativa

long contarQuadradosIterativo(int n, int m) {
    long totalQuadrados = 0;
    int limite = Math.min(n, m);
    for (int lado = 1; lado <= limite; lado++) {
        totalQuadrados += (long)(n - lado + 1) * (m - lado + 1);
    }
    return totalQuadrados;
}

Versão com Fórmula Fechada

long contarQuadradosFormula(int n, int m) {
    long a = Math.min(n, m);
    long b = Math.max(n, m);
    long quadrados = a * (a + 1) * (3 * b - a + cardena1) / 6;
    return quadrados;
}

Importante: Utilize o tipo long para todas as variáveis para evitar overflow. Para n=m=5000, os valores intermediários podem exceder o limite de 32 bits.

Comparação de Abordagens

Limitações e Considerações

As fórmulas apresentadas são válidas sob estas premissas:

• A grade é perfeitamente regular, sem células obstruídas.
• Os lados dos quadrados e retângulos são estritamente paralelos aos eixos da grade.
• Contamos todos os quadrados possíveis, independentemente do tamanho.

Para problemas com obstáculos, rotações de quadrados, ou contagens parciais, uma modelagem diferente será necessária.