. Matrix

542. 01 Matrix

Schwierigkeit:Mittel

Themen: Array, dynamische Programmierung, Breitensuche, Matrix

Gib bei einer m x n-Binärmatrixmatte den Abstand der nächsten 0 für jede Zelle zurück.

Der Abstand zwischen zwei Zellen mit einer gemeinsamen Kante beträgt 1.

Beispiel 1:

• Eingabe: mat = [[0,0,0],[0,1,0],[0,0,0]]
• Ausgabe: [[0,0,0],[0,1,0],[0,0,0]]

Beispiel 2:

• Eingabe: mat = [[0,0,0],[0,1,0],[1,1,1]]
• Ausgabe: [[0,0,0],[0,1,0],[1,2,1]]

Einschränkungen:

• m == mat.length
• n == mat[i].length
• 1 4
• 1 4
• mat[i][j] ist entweder 0 oder 1.
• Es gibt mindestens eine 0 in mat.

Hinweis: Diese Frage ist dieselbe wie 1765. Karte des höchsten Gipfels

Lösung:

Wir werden Breadth-First Search (BFS) mit mehreren Quellen verwenden, wobei alle 0 Zellen als Ausgangspunkte (Quellen) behandelt werden. Für jede 1-Zelle berechnen wir den Mindestabstand zur nächsten 0.

Lassen Sie uns diese Lösung in PHP implementieren: 542. 01 Matrix

<?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]]
?>

Erläuterung:

1. Initialisierung:

   • Das Distanzarray wird zunächst für alle Zellen mit PHP_INT_MAX initialisiert.
   • Alle 0 Zellen werden im Abstandsarray auf 0 gesetzt und der BFS-Warteschlange hinzugefügt.

2. Multi-Source-BFS:

   • Mithilfe einer Warteschlange führen wir BFS von allen 0 Zellen gleichzeitig aus.
   • Überprüfen Sie für jede Zelle in der Warteschlange ihre Nachbarn (oben, unten, links, rechts).
   • Wenn die Entfernung des Nachbarn verringert werden kann (distance[newRow][newCol] > currentDistance 1), aktualisieren Sie seine Entfernung und stellen Sie ihn in die Warteschlange.

3. Ausgabe:

   • Das Abstandsarray wird mit den Mindestabständen auf die nächste 0 für alle Zellen aktualisiert.

Eingabe und Ausgabe:

Eingabe 1:

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

Ausgabe 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
        )
)

Eingabe 2:

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

Ausgabe 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
        )
)

Diese Lösung ist effizient mit einer Zeitkomplexität von O(m × n), da jede Zelle einmal verarbeitet wird. Die Raumkomplexität beträgt aufgrund des Distanzarrays und der BFS-Warteschlange auch O(m × n).

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt von. Matrix. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!