Schiffe versenken (Sea Battle)
Du möchtest das Spiel „Schiffe versenken“ entwickeln. Zu Beginn des Spiels platziert jeder Spieler einige Schlachtschiffe auf einem Gitter an bestimmten Positionen. Jedes Schlachtschiff erstreckt sich in einer geraden Linie von bis , wobei die Verbindungslinie zwischen diesen Koordinaten immer rechtwinklig zu den Gitterseiten verläuft.
Als ersten Schritt möchtest du das Spielfeld prüfen, um sicherzustellen, dass die Spieler die Schlachtschiffe nicht zu dicht beieinander platzieren oder sich gar überschneiden. Zwischen jedem Schlachtschiff und seinen Nachbarn muss mindestens eine Zelle Wasser liegen. Es ist jedoch erlaubt, ein Schlachtschiff direkt am Rand zu platzieren, ohne dass dort ebenfalls eine Wasserzelle erforderlich ist.
Eingabe
Die erste Zeile der Eingabe enthält 3 ganze Zahlen:
•
n – die Anzahl der Schlachtschiffe (1 ≤ n ≤ 20),•
w – die Breite des Spielfelds (1 ≤ w ≤ 1000),•
h – die Höhe des Spielfelds (1 ≤ h ≤ 1000).Die nächsten
n Zeilen enthalten jeweils 4 ganze Zahlen – und (1 ≤ ≤ ≤ h) (1 ≤ ≤ ≤ w) – als Koordinaten für jedes Schlachtschiff.Ausgabe
Das Programm soll
Valid ausgeben, falls das Spielfeld gültig ist, und sonst Invalid.Beispiele
Eingabe | Ausgabe |
2 10 10
1 1 1 5
8 1 8 10 | Valid |
2 10 10
1 1 1 5
2 3 2 10 | Invalid |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB