Problema
Uma sequência é formada por k células em linha reta: da esquerda para a direita em uma linha, de cima para baixo em uma coluna ou ao longo de qualquer uma das diagonais. Multiplique os números de cada sequência e encontre a que tem o maior produto.
Implemente largest_product_in_grid(grid, k).
Entrada
grid: uma grade retangular de números; todas as linhas têm o mesmo tamanho.
k: o comprimento de uma sequência.
Saída
Retorne o maior produto entre todas as sequências de comprimento k. Se nenhuma sequência de comprimento k couber na grade em nenhuma direção, retorne 0.
Restrições
1 ≤ linhas, colunas ≤ 20; 0 ≤ grid[r][c] ≤ 99; 1 ≤ k ≤ 5
Exemplos
Entrada:
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
k = 2
Saída esperada:
expected = 72
Entrada:
std::vector<std::vector<long long>> grid = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
long long k = 2;
Saída esperada:
long long expected = 72;
Entrada:
long[][] grid = new long[][] {
new long[] {1, 2, 3},
new long[] {4, 5, 6},
new long[] {7, 8, 9}
};
long k = 2;
Saída esperada:
long expected = 72;
Explicação
A melhor sequência é 8 e 9 na última linha: 8 × 9 = 72. A diagonal 5, 9 dá só 45.
Entrada:
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
k = 3
Saída esperada:
expected = 504
Entrada:
std::vector<std::vector<long long>> grid = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
long long k = 3;
Saída esperada:
long long expected = 504;
Entrada:
long[][] grid = new long[][] {
new long[] {1, 2, 3},
new long[] {4, 5, 6},
new long[] {7, 8, 9}
};
long k = 3;
Saída esperada:
long expected = 504;
Explicação
A última linha dá 7 × 8 × 9 = 504, mais que a coluna da direita, 3 × 6 × 9 = 162, ou que qualquer diagonal.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Quatro direções bastam: direita, baixo, diagonal para baixo e à direita e diagonal para baixo e à esquerda. As outras repetem as mesmas sequências ao contrário.
Dica 2
A partir de cada célula inicial, verifique se a última célula da sequência ainda está dentro da grade.
Dica 3
Retorne 0 só quando nenhuma sequência de comprimento k couber.
Complexidade esperada
tempo O(rows × cols × k), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.