. Matrice

542. 01 Matrice

Difficulté :Moyen

Sujets :Array, programmation dynamique, recherche en largeur d'abord, matrice

Étant donné un tapis matriciel binaire m x n, renvoie la distance du 0 le plus proche pour chaque cellule.

La distance entre deux cellules partageant un bord commun est de 1.

Exemple 1 :

• Entrée : mat = [[0,0,0],[0,1,0],[0,0,0]]
• Sortie : [[0,0,0],[0,1,0],[0,0,0]]

Exemple 2 :

• Entrée : mat = [[0,0,0],[0,1,0],[1,1,1]]
• Sortie : [[0,0,0],[0,1,0],[1,2,1]]

Contraintes :

• m == mat.longueur
• n == mat[i].length
• 1 4
• 1 4
• mat[i][j] vaut 0 ou 1.
• Il y a au moins un 0 dans mat.

Remarque : Cette question est la même que celle de 1765. Carte du plus haut sommet

Solution :

Nous utiliserons la Bath-First Search (BFS) multi-sources, où toutes les cellules 0 sont traitées comme des points de départ (sources). Pour chaque cellule, nous calculons la distance minimale au 0 le plus proche.

Implémentons cette solution en PHP : 542. 01 Matrice

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

// Example usage:
$mat1 = [[0,0,0],[0,1,0],[0,0,0]];
$mat2 = [[0,0,0],[0,1,0],[1,1,1]];

echo updateMatrix($mat1) . "\n"; // Output: [[0,0,0],[0,1,0],[0,0,0]]
echo updateMatrix($mat2) . "\n"; // Output: [[0,0,0],[0,1,0],[1,2,1]]
?>

Explication:

1. Initialisation :

   • Le tableau de distance est initialement initialisé avec PHP_INT_MAX pour toutes les cellules.
   • Toutes les cellules 0 sont définies sur 0 dans le tableau de distance et ajoutées à la file d'attente BFS.

2. BFS multi-sources :

   • À l'aide d'une file d'attente, nous effectuons simultanément un BFS à partir des 0 cellules.
   • Pour chaque cellule de la file d'attente, vérifiez ses voisines (haut, bas, gauche, droite).
   • Si la distance du voisin peut être réduite (distance[newRow][newCol] > currentDistance 1), mettez à jour sa distance et mettez-la en file d'attente.

3. Sortie :

   • Le tableau de distance est mis à jour avec les distances minimales au 0 le plus proche pour toutes les cellules.

Entrée et sortie :

Entrée 1 :

$mat1 = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
];

Sortie 1 :

Array
(
    [0] => Array
        (
            [0] => 0
            [1] => 0
            [2] => 0
        )

    [1] => Array
        (
            [0] => 0
            [1] => 1
            [2] => 0
        )

    [2] => Array
        (
            [0] => 0
            [1] => 0
            [2] => 0
        )
)

Entrée 2 :

$mat2 = [
    [0, 0, 0],
    [0, 1, 0],
    [1, 1, 1]
];

Sortie 2 :

Array
(
    [0] => Array
        (
            [0] => 0
            [1] => 0
            [2] => 0
        )

    [1] => Array
        (
            [0] => 0
            [1] => 1
            [2] => 0
        )

    [2] => Array
        (
            [0] => 1
            [1] => 2
            [2] => 1
        )
)

Cette solution est efficace avec une complexité temporelle de O(m × n), car chaque cellule est traitée une fois. La complexité spatiale est également O(m × n) en raison du tableau de distance et de la file d'attente BFS.

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!