Maximale Anzahl von Fischen in einem Netz

2658. Maximale Anzahl von Fischen in einem Netz

Schwierigkeitsgrad: Medium

Themen: Array, Tiefen-First-Suche, Breite-First-Suche, Union Finden, Matrix

Sie erhalten ein 0-indexed 2D-Matrix-Gitter der Größe m x n, wobei (r, c):

darstellt

• a Land Zelle, wenn Gitter [r] [c] = 0 oder
• a Wasser Zelle enthält Gitter [R] [C] Fisch, wenn Gitter [r] [c] & gt; 0.

Ein Fischer kann in jeder Wasserzelle (r, c) beginnen und die folgenden Operationen jederzeit ausführen:

Fangen Sie alle Fische in der Zelle (r, c) oder
• auf
wechseln Sie zu einer benachbarten
• Wasser Zelle.

return

Die maximale Anzahl der Fische, die der Fischer fangen kann, wenn er seine Startzelle optimal wählt, oder 0, wenn keine Wasserzelle . vorhanden ist

und

benachbarte Zelle der Zelle (r, c) ist eine der Zellen (r, c 1), (r, c - 1), (r 1, c) oder (r - 1, c) Wenn es existiert.

Beispiel 1:

• Eingabe: grid = [0,2,1,0], [4,0,0,3], [1,0,0,4], [0,3,2,0] ]
• Ausgabe: 7
• Erläuterung: Der Fischer kann in der Zelle (1,3) beginnen und 3 Fische sammeln, dann zur Zelle (2,3) gehen und 4 Fische sammeln.

Beispiel 2:

• Eingabe: grid = [[1,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,1] ]
• Ausgabe: 1
• Erläuterung: Der Fischer kann mit Zellen (0,0) oder (3,3) beginnen und einen einzelnen Fisch sammeln.

Einschränkungen:

m == Grid.length
n == Gitter [i] .Length
1 & lt; = m, n & lt; = 10
0 & lt; = grid [i] [j] & lt; = 10

Hinweis:

DFS von jeder Zelle ungleich Null laufen.
Jedes Mal, wenn Sie zu Beginn eine Zelle auswählen, addieren Sie die Anzahl der Fische, die in den von Ihnen besuchten Zellen enthalten sind.

Lösung:

Das Problem besteht darin, die maximale Anzahl von Fischen zu finden, die ein Fischer fangen kann, indem er in einer Netzzelle in einem Netz beginnt. Der Fischer kann Fische in der aktuellen Zelle fangen und sich wiederholt zu einer benachbarten Wasserzelle (nach oben, links oder rechts) bewegen.

Schlüsselpunkte:

1. Das Netz enthält Zellen, die entweder Land (Wert 0) oder Wasser (Wert & GT; 0) sind.
2. Der Fischer kann sich nur in benachbarte Wasserzellen bewegen.
3. Das Ziel ist es, die maximale Anzahl von Fischsammeln aus der bestmöglichen Wasserzelle zu finden.

Ansatz:

1. Verwenden Sie Tiefe-First-Suche (DFS) , um alle möglichen Pfade aus jeder Wasserzelle zu untersuchen.
2. Führen Sie für jede nicht besuchte Wasserzelle ein DFS, um den Gesamtfisch in der angeschlossenen Komponente zu berechnen.
3. Verfolgen Sie die maximalen Fische, die von einer angeschlossenen Komponente gesammelt wurden.

Planen:

1. initialisieren Sie ein 2D -Besuchsarray, um zu verfolgen, ob eine Zelle untersucht wurde.
2. durch jede Zelle im Raster iterieren.
3. Wenn die Zelle Wasser enthält und nicht besucht wird:
   • Führen Sie ein DFS aus dieser Zelle aus.
   • akkumulieren die Gesamtfische in den verbundenen Wasserzellen.
   • Aktualisieren Sie die bisher gesammelten maximalen Fische.
4. RECHEN SIE DIE MALIAL FISH ZUGEN, DASS ALLE ZEILEN ERSCHLUSS.

implementieren wir diese Lösung in PHP: 2658. Maximale Anzahl von Fischen in einem Netz

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

/**
 * Helper function for DFS
 * @param $r
 * @param $c
 * @param $grid
 * @param $visited
 * @param $rows
 * @param $cols
 * @param $directions
 * @return array|bool|int|int[]|mixed|null
 */
function dfs($r, $c, &$grid, &$visited, $rows, $cols, $directions) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]];
echo getMaxFish($grid); // Output: 7

// Example 2
$grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]];
echo getMaxFish($grid); // Output: 1
?>

Erläuterung:

DFS -Implementierung:

• für jede Wasserzelle (r, c) erforschen Sie rekursiv seine Nachbarn, wenn sie sind:
  • Innerhalb der Gittergrenzen.
  • nicht besucht.
  • Wasserzellen (Wert & gt; 0).
• akkumulieren die Fischzahl während der Rekursion.

Schritte:

1. Beginnen Sie von einer Wasserzelle und markieren Sie sie wie besucht.
2. besuchen Sie rekursiv seine gültigen Nachbarn und addieren Sie die Fischzahl.
3. Rückgabe die Gesamtfischzahl für die angeschlossene Komponente.

Beispielhandlung:

Beispieleingabe:

$grid = [
    [0, 2, 1, 0],
    [4, 0, 0, 3],
    [1, 0, 0, 4],
    [0, 3, 2, 0]
];

Ausführung:

1. Beginnen Sie bei (1, 3) (Wert = 3). DFS laufen:
   • (1, 3) → (2, 3) (Wert = 4).
   • Gesamtfisch = 3 4 = 7.
2. Erforschen Sie andere Wasserzellen, aber keine verbundene Komponente hat eine höhere Gesamtzahl der Fische.
3. Ausgabe: 7.

Zeitkomplexität:

• dfs traversal: Jede Zelle wird einmal besucht → o (M × n).
• Gesamtkomplexität: o (m × n), wobei m und n Gitterabmessungen sind.

Ausgabe für Beispiele:

• Beispiel 1: 7
• Beispiel 2: 1

Die Lösung verwendet effizient DFS, um verbundene Komponenten von Wasserzellen zu untersuchen und den maximalen Fisch zu berechnen, der von einem Fischer aus jeder Wasserzelle ausgeht. Dieser Ansatz sorgt für eine optimale Erkundung und funktioniert gut für die angegebenen Einschränkungen.

Kontaktlinks

Wenn Sie diese Serie hilfreich gefunden haben, sollten Sie das repository einen Stern auf Github geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken teilen? Ihre Unterstützung würde mir viel bedeuten!

Wenn Sie mehr hilfreiche Inhalte wie diesen wünschen, können Sie mir gerne folgen:

• linkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonMaximale Anzahl von Fischen in einem Netz. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!