Zählen Sie unbewachte Zellen im Raster

2257. Zählen Sie unbewachte Zellen im Raster

Schwierigkeit:Mittel

Themen:Array, Matrix, Simulation

Sie erhalten zwei ganze Zahlen m und n, die ein 0-indiziertes m x n-Gitter darstellen. Sie erhalten außerdem zwei ganzzahlige 2D-Arrays „guards“ und „walls“, wobei „guards[i] = [row_i, col_i]“ und „walls[j] = [row_{j, col}j_{] repräsentieren die Positionen des i}ten ^{Wächters und j}th^{Wand bzw.}

Ein Wachmann kann

jede Zelle in den vier Himmelsrichtungen (Norden, Osten, Süden oder Westen) von seiner Position aus sehen, es sei denn, er wird durch eine Mauer oder einen anderen Wachmann behindert. Eine Zelle ist bewacht, wenn es mindestens einen Wächter gibt, der sie sehen kann.

Gibt

die Anzahl der unbesetzten Zellen zurück, die nicht bewacht sind.

Beispiel 1:

• Eingabe: m = 4, n = 6, Wachen = [[0,0],[1,1],[2,3]], Wände = [[0,1],[2, 2],[1,4]]
• Ausgabe: 7
• Erklärung: Die geschützten und ungeschützten Zellen sind im obigen Diagramm in Rot bzw. Grün dargestellt.
  Es gibt insgesamt 7 unbewachte Zellen, also geben wir 7 zurück.

Beispiel 2:

• Eingabe: m = 3, n = 3, Wachen = [[1,1]], Wände = [[0,1],[1,0],[2,1],[1, 2]]
• Ausgabe: 4
• Erklärung: Die unbewachten Zellen sind im obigen Diagramm grün dargestellt.
  Es gibt insgesamt 4 unbewachte Zellen, also geben wir 4 zurück.

Einschränkungen:

1 <= m, n <= 10
• 5
2 <= m * n <= 10
• 5
1 <= Guards.Length, Walls.Length <= 5 * 10
• 4
2 <= Guards.Length Walls.Length <= m * n
guards[i].length == walles[j].length == 2
0 <= Zeile
• i_{, Zeile}j _{< m}
0 <= col
• i_{, col}j _{< n}
Alle Positionen in Wachen und Mauern sind
• einzigartig.

Hinweis:

Erstellen Sie ein 2D-Array zur Darstellung des Rasters. Können Sie die Kacheln markieren, die für einen Wachmann sichtbar sind?
Durchlaufen Sie die Wachen und rücken Sie für jede der 4 Richtungen das aktuelle Plättchen vor und markieren Sie das Plättchen. Wann sollten Sie mit dem Voranschreiten aufhören?

Lösung:

Wir müssen die Zellen markieren, die von mindestens einem Wächter bewacht werden. Die Wachen können in vier Himmelsrichtungen sehen (Norden, Süden, Osten und Westen), ihre Sicht wird jedoch durch Mauern blockiert. Wir können diesen Prozess simulieren und die Anzahl der unbewachten Zellen zählen.

Ansatz:

1. Erstellen Sie ein Gitter: Wir können das Gitter als 2D-Array darstellen, wobei jede Zelle entweder eine Wand, ein Schutz oder leer sein kann.
2. Bewachte Zellen markieren: Iterieren Sie für jeden Wächter in die vier Richtungen (Norden, Süden, Osten, Westen) und markieren Sie alle Zellen, die er sehen kann, und halten Sie an, wenn wir auf eine Wand oder einen anderen Wächter stoßen.
3. Ungeschützte Zellen zählen: Zählen Sie nach dem Markieren der geschützten Zellen, wie viele Zellen nicht geschützt sind und keine Wände sind.

Schritte:

1. Gitterinitialisierung: Erstellen Sie ein 2D-Array zur Darstellung des Gitters. Markieren Sie Zellen mit Wänden, Wachen und bewachten Bereichen, während wir iterieren.

2. Simulation der Schutzabdeckung:

   • Wächter können in vier Richtungen sehen (Norden, Süden, Osten, Westen).
   • Markieren Sie die Zellen, die von jedem Wächter bewacht werden, bis Sie auf eine Wand oder einen anderen Wächter stoßen.

3. Unbewachte Zellen zählen: Nachdem Sie alle Wächter verarbeitet haben, zählen Sie Zellen, die weder Wände, Wächter noch bewacht sind.

Lassen Sie uns diese Lösung in PHP implementieren: 2257. Zählen Sie unbewachte Zellen im Raster

  
  
  Erläuterung:





Initialisierung:


Das Raster wird für leere Zellen mit 0 initialisiert. Wände und Wachen sind mit eindeutigen Konstanten gekennzeichnet.



Wächtersimulation:


Simulieren Sie für jeden Wächter eine Bewegung in alle vier Richtungen und markieren Sie Zellen als bewacht, bis Sie auf eine Wand oder einen anderen Wächter stoßen.



Ungeschützte Zellen zählen:

Nachdem alle Wachen verarbeitet wurden, durchlaufen Sie das Raster und zählen die Zellen, die immer noch als 0 markiert sind.





  
  
  Leistung:



Zeitliche Komplexität: O(m x n g x d), wobei g die Anzahl der Wachen und d ist  ist die Anzahl der Zellen in der Richtung, in die sich jeder Wachmann bewegen kann.
Raumkomplexität: O(m x n) für das Gitter.



  
  
  Zeitkomplexität:




Gitterinitialisierung: _O(m * n), wobei _m und n sind die Abmessungen des Gitters.

Markierungswächtersicht: Jeder Wächter überprüft höchstens die Länge der Zeile oder Spalte in den vier Richtungen. Für jede Wache ist es also O(m n).

Ungeschützte Zellen zählen: O(m * n).


Daher beträgt die Gesamtkomplexität O(m * n), was angesichts der Problembeschränkungen effizient ist.


  
  
  Randfälle:



Wenn keine Wachen oder Mauern vorhanden sind, ist das gesamte Gitter unbewacht.
Wenn alle Zellen entweder geschützt oder ummauert sind, sind das Ergebnis 0 ungeschützte Zellen.


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 vonZählen Sie unbewachte Zellen im Raster. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!