Suppression minimale des obstacles pour atteindre le coin

2290. Suppression minimale des obstacles pour atteindre le coin

Difficulté : Difficile

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

Vous recevez une grille de tableau d'entiers 2D indexée à 0 de taille m x n. Chaque cellule a l'une des deux valeurs suivantes :

• 0 représente une cellule vide,
• 1 représente un obstacle qui peut être supprimé.

Vous pouvez vous déplacer vers le haut, le bas, la gauche ou la droite depuis et vers une cellule vide.

Renvoyer le nombre minimum d'obstacles à supprimer pour pouvoir passer du coin supérieur gauche (0, 0) au coin inférieur droit coin (m - 1, n - 1).

Exemple 1 :

• Entrée : grille = [[0,1,1],[1,1,0],[1,1,0]]
• Sortie : 2
• Explication : On peut supprimer les obstacles en (0, 1) et (0, 2) pour créer un chemin de (0, 0) à (2, 2).
  • On peut montrer qu'il faut supprimer au moins 2 obstacles, donc on en retourne 2.
  • Notez qu'il peut exister d'autres moyens de supprimer 2 obstacles pour créer un chemin.

Exemple 2 :

• Entrée : grille = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
• Sortie : 0
• Explication : On peut passer de (0, 0) à (2, 4) sans supprimer aucun obstacle, on renvoie donc 0.

Contraintes :

• m == grille.longueur
• n == grille[i].longueur
• 1 5
• 2 5
• grille[i][j] vaut 0 ou 1.
• grille[0][0] == grille[m - 1][n - 1] == 0

Indice :

1. Modélisez la grille sous forme de graphique où les cellules sont des nœuds et les bords sont entre les cellules adjacentes. Les bords des cellules avec des obstacles ont un coût de 1 et tous les autres bords ont un coût de 0.
2. Pourriez-vous utiliser la recherche en largeur 0-1 ou l'algorithme de Dijkstra ?

Solution :

Nous devons modéliser ce problème en utilisant un graphique où chaque cellule de la grille est un nœud. Le but est de naviguer du coin supérieur gauche (0, 0) vers le coin inférieur droit (m-1, n-1), tout en minimisant le nombre d'obstacles (1s) que nous devons supprimer.

Approche:

1. Représentation graphique :

   • Chaque cellule de la grille est un nœud.
   • Le mouvement entre les cellules adjacentes (haut, bas, gauche, droite) est traité comme un bord.
   • Si un bord traverse une cellule avec un 1 (obstacle), le coût est de 1 (supprimer l'obstacle), et s'il traverse un 0 (cellule vide), le coût est de 0.

2. Choix de l'algorithme :

   • Puisque nous devons minimiser le nombre d'obstacles supprimés, nous pouvons utiliser le 0-1 BFS (Breadth-First Search avec un deque) ou l'algorithme de Dijkstra avec une file d'attente prioritaire.
   • 0-1 BFS convient ici car chaque bord a un coût de 0 ou de 1.

3. 0-1 BFS :

   • Nous utilisons un deque (file d'attente à double extrémité) pour traiter des nœuds avec des coûts différents :
     • Poussez les cellules de coût 0 vers l'avant du deque.
     • Poussez les cellules de coût 1 à l'arrière du deque.
   • L'idée est d'explorer la grille et de toujours élargir le chemin qui ne nécessite pas d'abord la suppression des obstacles, et de supprimer les obstacles uniquement lorsque cela est nécessaire.

Implémentons cette solution en PHP : 2290. Suppression minimale des obstacles pour atteindre le coin

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

// Test Case 1
$grid1 = [
    [0, 1, 1],
    [1, 1, 0],
    [1, 1, 0]
];
echo minimumObstacles($grid1) . PHP_EOL; // Output: 2

// Test Case 2
$grid2 = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0]
];
echo minimumObstacles($grid2) . PHP_EOL; // Output: 0
?>

Explication:

1. Analyse des entrées :

   • La grille est prise comme un tableau 2D.
   • Les lignes et les colonnes sont calculées pour la vérification des limites.

2. Mise en œuvre de Deque :

   • SplDoublyLinkedList est utilisé pour simuler le deque. Il prend en charge l'ajout d'éléments à l'avant (unshift) ou à l'arrière (push).

3. Tableau visité :

   • Garde une trace des cellules déjà visitées pour éviter un traitement redondant.

4. 0-1 Logique BFS :

   • Commencez à partir de (0, 0) avec un coût de 0.
   • Pour chaque cellule voisine :
     • S'il est vide (grid[nx][ny] == 0), ajoutez-le au début du deque avec le même coût.
     • Si c'est un obstacle (grid[nx][ny] == 1), ajoutez-le au dos du deque avec un coût incrémenté.

5. Renvoyer le résultat :

   • Lorsque le coin inférieur droit est atteint, renvoyez le coût.
   • Si aucun chemin valide n'existe (bien que le problème en garantisse un), renvoie -1.

---

Complexité:

• Complexité temporelle : O(m x n), où m est le nombre de lignes et n est le nombre de colonnes. Chaque cellule est traitée une fois.
• Complexité spatiale : O(m x n), pour le tableau visité et deque.

Cette implémentation fonctionne efficacement dans les limites données.

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!