Problème
Un alignement est une suite de k cases en ligne droite : de gauche à droite sur une ligne, de haut en bas dans une colonne, ou selon l'une des deux diagonales. Multipliez les nombres de chaque alignement et trouvez celui dont le produit est le plus grand.
Implémentez largest_product_in_grid(grid, k).
Entrée
grid : une grille rectangulaire de nombres ; toutes les lignes ont la même longueur.
k : la longueur d'un alignement.
Sortie
Renvoyez le plus grand produit parmi tous les alignements de longueur k. Si aucun alignement de longueur k ne tient dans la grille, quelle que soit la direction, renvoyez 0.
Contraintes
1 ≤ lignes, colonnes ≤ 20 ; 0 ≤ grid[r][c] ≤ 99 ; 1 ≤ k ≤ 5
Exemples
Entrée :
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
k = 2
Sortie attendue :
expected = 72
Entrée :
std::vector<std::vector<long long>> grid = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
long long k = 2;
Sortie attendue :
long long expected = 72;
Entrée :
long[][] grid = new long[][] {
new long[] {1, 2, 3},
new long[] {4, 5, 6},
new long[] {7, 8, 9}
};
long k = 2;
Sortie attendue :
long expected = 72;
Explication
Le meilleur alignement est 8 et 9 sur la dernière ligne : 8 × 9 = 72. La diagonale 5, 9 ne donne que 45.
Entrée :
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
k = 3
Sortie attendue :
expected = 504
Entrée :
std::vector<std::vector<long long>> grid = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
long long k = 3;
Sortie attendue :
long long expected = 504;
Entrée :
long[][] grid = new long[][] {
new long[] {1, 2, 3},
new long[] {4, 5, 6},
new long[] {7, 8, 9}
};
long k = 3;
Sortie attendue :
long expected = 504;
Explication
La dernière ligne donne 7 × 8 × 9 = 504, plus que la colonne de droite 3 × 6 × 9 = 162 ou que n'importe quelle diagonale.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Quatre directions suffisent : droite, bas, bas-droite et bas-gauche. Les autres parcourent les mêmes alignements à l'envers.
Indice 2
Depuis chaque case de départ, vérifiez que la dernière case de l'alignement est encore dans la grille.
Indice 3
Ne renvoyez 0 que si aucun alignement de longueur k ne tient dans la grille.
Complexité attendue
temps O(rows × cols × k), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.