Tous les défis
Moyen 0 résolus 0 % de réussite

Plus grand produit dans une grille

Trouver le plus grand produit de k nombres alignés dans une grille.

Ce que vous allez apprendre

  • Parcourir une grille dans quatre directions avec des couples de pas
  • Vérifier les bornes avant de lire un alignement
  • Mettre à jour un maximum au fil du parcours

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

Exemple 1
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.

Exemple 2
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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.