Grid-Spiel

2017. Rasterspiel

Schwierigkeit:Mittel

Themen:Array, Matrix, Präfixsumme

Sie erhalten ein 0-indiziertes 2D-Array-Gitter der Größe 2 x n, wobei Grid[r][c] die Anzahl der Punkte an Position (r, c) auf der Matrix darstellt. Auf dieser Matrix spielen zwei Roboter ein Spiel.

Beide Roboter starten zunächst bei (0, 0) und wollen (1, n-1) erreichen. Jeder Roboter darf sich nur nach rechts ((r, c) nach (r, c 1)) oder nach unten ((r, c) nach (r 1, c)) bewegen.

Zu Beginn des Spiels bewegt sich der erste Roboter von (0, 0) nach (1, n-1) und sammelt dabei alle Punkte von den Zellen auf seinem Weg. Für alle Zellen (r, c), die auf dem Pfad durchlaufen werden, wird Grid[r][c] auf 0 gesetzt. Dann bewegt sich der zweite Roboter von (0, 0) nach (1, n-1). ) und sammelt die Punkte auf seinem Weg. Beachten Sie, dass sich ihre Pfade kreuzen können.

Der erste Roboter möchte die Anzahl der vom zweiten Roboter gesammelten Punkte minimieren. Im Gegensatz dazu möchte der zweite Roboter die Anzahl der gesammelten Punkte maximieren. Wenn beide Roboter optimal spielen, geben Sie die Anzahl der Punkte zurück, die der zweite Roboter gesammelt hat.

Beispiel 1:

• Eingabe: Gitter = [[2,5,4],[1,5,1]]
• Ausgabe: 4
• Erklärung: Der optimale Weg des ersten Roboters wird in Rot und der optimale Weg des zweiten Roboters in Blau angezeigt.
  • Die vom ersten Roboter besuchten Zellen werden auf 0 gesetzt.
  • Der zweite Roboter sammelt 0 0 4 0 = 4 Punkte.

Beispiel 2:

• Eingabe: Gitter = [[3,3,1],[8,5,2]]
• Ausgabe: 4
• Erklärung: Der optimale Weg des ersten Roboters wird in Rot und der optimale Weg des zweiten Roboters in Blau angezeigt.
  • Die vom ersten Roboter besuchten Zellen werden auf 0 gesetzt.
  • Der zweite Roboter sammelt 0 3 1 0 = 4 Punkte.

Beispiel 3:

• Eingabe: Gitter = [[1,3,1,15],[1,3,3,1]]
• Ausgabe: 7
• Erklärung: Der optimale Weg des ersten Roboters wird in Rot und der optimale Weg des zweiten Roboters in Blau angezeigt.
  • Die vom ersten Roboter besuchten Zellen werden auf 0 gesetzt.
  • Der zweite Roboter sammelt 0 1 3 3 0 = 7 Punkte.

Einschränkungen:

• grid.length == 2
• n == grid[r].length
• 1 4
• 1 5

Hinweis:

1. Es gibt n Möglichkeiten, wann der erste Roboter in die zweite Reihe wechselt.
2. Können wir Präfixsummen verwenden, um dieses Problem zu lösen?

Lösung:

Wir verwenden den folgenden Ansatz:

1. Präfixsummenberechnung: Wir berechnen die Präfixsummen für beide Zeilen des Rasters, um die Punktsumme für jedes Unterarray effizient zu berechnen.

2. Optimale Bewegung simulieren:

   • Der erste Roboter bestimmt seinen Weg, um die für den zweiten Roboter verbleibenden Punkte zu minimieren.
   • Bei jedem Spaltenübergang kann sich der erste Roboter nach unten bewegen und so das Raster in zwei Segmente aufteilen:
     • Obere verbleibende Punkte: Punkte in der obersten Zeile nach der Übergangsspalte.
     • Niedrigere verbleibende Punkte: Punkte in der unteren Zeile vor der Übergangsspalte.

3. Minimierung der maximalen Punkte für den zweiten Roboter:

   • Berechnen Sie bei jedem Übergang die maximale Punktzahl, die der zweite Roboter nach dem Weg des ersten Roboters sammeln kann.
   • Verfolgen Sie das Minimum dieser Maximumwerte über alle Übergänge hinweg.

Lassen Sie uns diese Lösung in PHP implementieren: 2017. Rasterspiel

<?php function gridGame($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$grid1 = [[2, 5, 4], [1, 5, 1]];
$grid2 = [[3, 3, 1], [8, 5, 2]];
$grid3 = [[1, 3, 1, 15], [1, 3, 3, 1]];

echo gridGame($grid1) . "\n"; // Output: 4
echo gridGame($grid2) . "\n"; // Output: 4
echo gridGame($grid3) . "\n"; // Output: 7
?>

Erläuterung:

1. Präfixsummenberechnung:

   • prefixTop und prefixBottom speichern kumulative Summen für die obere bzw. untere Zeile.
   • Diese ermöglichen effiziente Bereichssummenberechnungen.

2. Simulation des Pfades des ersten Roboters:

   • Bei jeder Spalte i kann der erste Roboter entscheiden, sich nach Spalte i nach unten zu bewegen.
   • Dadurch wird das Raster in zwei Bereiche aufgeteilt:
     • Oberste Zeile nach Spalte i (gesammelte Punkte: prefixTop[n] - prefixTop[i 1]).
     • Unterste Zeile vor Spalte i (gesammelte Punkte: prefixBottom[i]).

3. Die optimalen Punkte des zweiten Roboters:

   • Der zweite Roboter übernimmt das Maximum der beiden verbleibenden Regionen.
   • Wir verfolgen das Minimum dieser Maximumwerte für alle möglichen Übergänge.

4. Komplexität:

   • Zeitkomplexität: O(n), da wir Präfixsummen berechnen und das Gitter einmal durchlaufen.
   • Raumkomplexität: O(n), aufgrund von Präfix-Summen-Arrays.

Beispiel-Komplettlösung

Eingabe: Gitter = [[2, 5, 4], [1, 5, 1]]

• Präfixsummen:
  • prefixTop = [0, 2, 7, 11]
  • prefixBottom = [0, 1, 6, 7]
• Übergangspunkte:
  • i = 0: Oben verbleibend = 11 - 7 = 9, Unten verbleibend = 0 → Zweiter Roboter = 9.
  • i = 1: Oben verbleibend = 11 - 11 = 4, Unten verbleibend = 1 → Zweiter Roboter = 4.
  • i = 2: Oben verbleibend = 0, Unten verbleibend = 6 → Zweiter Roboter = 6.
• Mindestpunktzahl für den zweiten Roboter: min(9, 4, 6) = 4.

Dies entspricht der erwarteten Ausgabe.

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 vonGrid-Spiel. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!