Coût minimum pour créer au moins un chemin valide dans une grille

1368. Coût minimum pour créer au moins un chemin valide dans une grille

Difficulté : Difficile

Sujets : Tableau, recherche en largeur d'abord, graphique, tas (file d'attente prioritaire), matrice, chemin le plus court

Étant donné une grille m x n. Chaque cellule de la grille comporte un signe pointant vers la cellule suivante que vous devriez visiter si vous êtes actuellement dans cette cellule. Le signe de la grille[i][j] peut être :

• 1 ce qui signifie aller dans la cellule de droite. (c'est-à-dire passer de la grille[i][j] à la grille[i][j 1])
• 2 ce qui signifie aller dans la cellule à gauche. (c'est-à-dire passer de la grille[i][j] à la grille[i][j - 1])
• 3, ce qui signifie aller à la cellule inférieure. (c'est-à-dire passer de la grille[i][j] à la grille[i 1][j])
• 4 ce qui signifie aller à la cellule supérieure. (c'est-à-dire passer de la grille[i][j] à la grille[i - 1][j])

Remarquez qu'il peut y avoir des signes sur les cellules de la grille qui pointent vers l'extérieur de la grille.

Vous commencerez initialement par la cellule supérieure gauche (0, 0). Un chemin valide dans la grille est un chemin qui part de la cellule supérieure gauche (0, 0) et se termine dans la cellule inférieure droite (m - 1, n - 1) en suivant les panneaux sur la grille. Le chemin valide ne doit pas nécessairement être le plus court.

Vous pouvez modifier le signe sur une cellule avec un coût = 1. Vous ne pouvez modifier le signe sur une cellule qu'une seule fois.

Renvoyer le coût minimum pour que la grille ait au moins un chemin valide.

Exemple 1 :

• Entrée : grille = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2] ]
• Sortie : 3
• Explication : Vous commencerez au point (0, 0). Le chemin vers (3, 3) est le suivant. (0, 0) ---> (0, 1) ---> (0, 2) ---> (0, 3)
• changez la flèche vers le bas avec coût = 1 ---> (1, 3) ---> (1, 2) ---> (1, 1) ---> (1, 0)
• changez la flèche vers le bas avec coût = 1 ---> (2, 0) ---> (2, 1) ---> (2, 2) ---> (2, 3)
• changez la flèche vers le bas avec coût = 1 ---> (3, 3) Le coût total = 3.

Exemple 2 :

• Entrée : grille = [[1,1,3],[3,2,2],[1,1,4]]
• Sortie : 0
• Explication : Vous pouvez suivre le chemin de (0, 0) à (2, 2).

Exemple 3 :

• Entrée : grille = [[1,2],[4,3]]
• Sortie : 1

Contraintes :

• m == grille.longueur
• n == grille[i].longueur
• 1
• 1

Indice :

1. Construisez un graphique où la grille[i][j] est connectée aux quatre cellules latérales adjacentes avec un bord pondéré. le poids est de 0 si le signe pointe vers la cellule adjacente ou de 1 sinon.
2. Est-ce que BFS à partir de (0, 0) visite d'abord tous les bords avec un poids = 0. la réponse est la distance à (m -1, n - 1).

Solution :

Nous pouvons utiliser l'approche 0-1 BFS. L'idée est de parcourir la grille à l'aide d'un deque (file d'attente à double extrémité) où le coût de modification de la direction détermine si une cellule est ajoutée à l'avant ou à l'arrière du deque. La grille est traitée comme un graphique où chaque cellule a des bords pondérés selon que sa direction actuelle correspond au mouvement de ses voisines.

Implémentons cette solution en PHP : 1368. Coût minimum pour créer au moins un chemin valide dans une grille

<?php /**
 * @param Integer[][] $grid
 * @return Integer
 */
function minCost($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Test Cases
$Coût minimum pour créer au moins un chemin valide dans une grille = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]];
echo minCost($Coût minimum pour créer au moins un chemin valide dans une grille) . "\n"; // Output: 3

$Coût minimum pour créer au moins un chemin valide dans une grille = [[1,1,3],[3,2,2],[1,1,4]];
echo minCost($Coût minimum pour créer au moins un chemin valide dans une grille) . "\n"; // Output: 0

$Coût minimum pour créer au moins un chemin valide dans une grille = [[1,2],[4,3]];
echo minCost($Coût minimum pour créer au moins un chemin valide dans une grille) . "\n"; // Output: 1
?>

Explication:

1. Cartographie des directions : Chaque direction (1 pour la droite, 2 pour la gauche, 3 pour le bas, 4 pour le haut) est mappée à un tableau de deltas de mouvement [dx, dy].

2. 0-1 BFS :

   • Un deque est utilisé pour prioriser les cellules à moindre coût. Les cellules qui ne nécessitent pas de modification de direction sont ajoutées à l'avant (unshift), tandis que celles qui nécessitent une modification sont ajoutées à l'arrière (mise en file d'attente).
   • Cela garantit que les cellules sont traitées par ordre croissant de coût.

3. Tableau de distance : Un tableau 2D $dist garde une trace du coût minimum pour atteindre chaque cellule. Il est initialisé avec PHP_INT_MAX pour toutes les cellules sauf la cellule de départ (0, 0).

4. Poids des bords :

   • Si le signe de la cellule actuelle correspond à la direction prévue, le coût reste le même.
   • Sinon, la modification de la direction entraîne un coût de 1.

5. Terminaison : La boucle se termine une fois que toutes les cellules ont été traitées. Le résultat est la valeur en $dist[$m - 1][$n - 1], représentant le coût minimum pour atteindre le coin inférieur droit.

Complexité:

• Complexité temporelle : O(m × n), puisque chaque cellule est traitée une fois.
• Complexité spatiale : O(m × n), pour le tableau de distance et deque.

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!