Jeu de grille

2017. Jeu de grille

Difficulté :Moyen

Sujets : Tableau, Matrice, Somme de préfixe

Vous recevez une grille de tableau 2D indexée 0 de taille 2 x n, où grille[r][c] représente le nombre de points en position (r, c) sur la matrice. Deux robots jouent à un jeu sur cette matrice.

Les deux robots commencent initialement à (0, 0) et veulent atteindre (1, n-1). Chaque robot ne peut se déplacer que vers la droite ((r, c) vers (r, c 1)) ou vers le bas ((r, c) vers (r 1, c)).

Au début du jeu, le premier robot se déplace de (0, 0) à (1, n-1), récupérant tous les points des cellules sur son passage. Pour toutes les cellules (r, c) parcourues sur le chemin, grid[r][c] est mis à 0. Ensuite, le second robot se déplace de (0, 0) à (1, n-1 ), récupérant les points sur son parcours. Notez que leurs chemins peuvent se croiser.

Le premier robot veut minimiser le nombre de points récoltés par le deuxième robot. En revanche, le deuxième robot souhaite maximiser le nombre de points qu'il collecte. Si les deux robots jouent de manière optimale, retournez le nombre de points collectés par le deuxième robot.

Exemple 1 :

• Entrée : grille = [[2,5,4],[1,5,1]]
• Sortie : 4
• Explication : Le chemin optimal emprunté par le premier robot est indiqué en rouge, et le chemin optimal emprunté par le deuxième robot est indiqué en bleu.
  • Les cellules visitées par le premier robot sont mises à 0.
  • Le deuxième robot récoltera 0 0 4 0 = 4 points.

Exemple 2 :

• Entrée : grille = [[3,3,1],[8,5,2]]
• Sortie : 4
• Explication : Le chemin optimal emprunté par le premier robot est indiqué en rouge, et le chemin optimal emprunté par le deuxième robot est indiqué en bleu.
  • Les cellules visitées par le premier robot sont mises à 0.
  • Le deuxième robot récoltera 0 3 1 0 = 4 points.

Exemple 3 :

• Entrée : grille = [[1,3,1,15],[1,3,3,1]]
• Sortie :7
• Explication : Le chemin optimal emprunté par le premier robot est indiqué en rouge, et le chemin optimal emprunté par le deuxième robot est indiqué en bleu.
  • Les cellules visitées par le premier robot sont mises à 0.
  • Le deuxième robot récoltera 0 1 3 3 0 = 7 points.

Contraintes :

• grid.length == 2
• n == grille[r].longueur
• 1 4
• 1 5

Indice :

1. Il y a n choix lorsque le premier robot passe à la deuxième rangée.
2. Pouvons-nous utiliser des sommes de préfixes pour aider à résoudre ce problème ?

Solution :

Nous utiliserons l'approche suivante :

1. Calcul de la somme des préfixes : Nous calculerons les sommes des préfixes pour les deux lignes de la grille afin de calculer efficacement la somme des points pour n'importe quel sous-tableau.

2. Simulation d'un mouvement optimal :

   • Le premier robot détermine son chemin pour minimiser les points restants pour le deuxième robot.
   • A chaque transition de colonne, le premier robot peut choisir de descendre, divisant la grille en deux segments :
     • Points supérieurs restants : points dans la rangée supérieure après la colonne de transition.
     • Points restants inférieurs : points dans la rangée du bas avant la colonne de transition.

3. Minimiser le maximum de points pour le deuxième robot :

   • A chaque transition, calculez le maximum de points que le deuxième robot peut récolter après le parcours du premier robot.
   • Suivez le minimum de ces maximums dans toutes les transitions.

Implémentons cette solution en PHP : 2017. Jeu de grille

<?php function gridGame($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$grid1 = [[2, 5, 4], [1, 5, 1]];
$grid2 = [[3, 3, 1], [8, 5, 2]];
$grid3 = [[1, 3, 1, 15], [1, 3, 3, 1]];

echo gridGame($grid1) . "\n"; // Output: 4
echo gridGame($grid2) . "\n"; // Output: 4
echo gridGame($grid3) . "\n"; // Output: 7
?>

Explication:

1. Calcul de la somme des préfixes :

   • prefixTop et prefixBottom stockent respectivement les sommes cumulées pour les lignes du haut et du bas.
   • Ceux-ci permettent des calculs efficaces de somme de plage.

2. Simuler le chemin du premier robot :

   • A chaque colonne i, le premier robot peut décider de descendre après la colonne i.
   • Cela divise la grille en deux régions :
     • Ligne du haut après la colonne i (points collectés : prefixTop[n] - prefixTop[i 1]).
     • Ligne du bas avant la colonne i (points collectés : prefixBottom[i]).

3. Points optimaux du deuxième robot :

   • Le deuxième robot prendra le maximum des deux régions restantes.
   • Nous suivons le minimum de ces maximums pour toutes les transitions possibles.

4. Complexité :

   • Complexité temporelle : O(n), car nous calculons les sommes des préfixes et parcourons la grille une fois.
   • Complexité spatiale : O(n), en raison des tableaux de somme de préfixes.

Exemple de procédure pas à pas

Entrée : grille = [[2, 5, 4], [1, 5, 1]]

• Sommes des préfixes :
  • préfixeTop = [0, 2, 7, 11]
  • prefixBottom = [0, 1, 6, 7]
• Points de transition :
  • i = 0 : Haut restant = 11 - 7 = 9, Bas restant = 0 → Deuxième Robot = 9.
  • i = 1 : Haut restant = 11 - 11 = 4, Bas restant = 1 → Deuxième Robot = 4.
  • i = 2 : Haut restant = 0, Bas restant = 6 → Deuxième robot = 6.
• Points minimum pour le deuxième robot : min(9, 4, 6) = 4.

Cela correspond au résultat attendu.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!