Sea Battle
Stai cercando di sviluppare il gioco “Sea Battle (Battaglia Navale)”. All'inizio di questa partita, ogni giocatore colloca alcune corazzate su una griglia in posizioni specifiche. Ogni corazzata si estende in linea retta da a , dove la retta che collega queste coordinate è sempre perpendicolare ai margini della griglia.
Come primo passo, desideri verificare la griglia per assicurarti che i giocatori non posizionino le corazzate troppo vicine tra loro o addirittura che non si intersechino. Ogni corazzata deve avere almeno una cella di acqua che la separi da un’altra nave. Non è invece necessario lasciare alcuno spazio tra una corazzata e il bordo della griglia.
Input
La prima riga dell’input contiene 3 interi:
n (il numero di corazzate, 1 ≤ n ≤ 20), w (la larghezza del campo di battaglia, 1 ≤ w ≤ 1000) e h (l’altezza del campo di battaglia, 1 ≤ h ≤ 1000).Le successive n righe contengono 4 interi: e (1 ≤ ≤ ≤ h) (1 ≤ ≤ ≤ w), ovvero le coordinate di ogni corazzata.
Output
Il programma deve stampare
Valid se la griglia è valida e Invalid altrimenti.Esempi
Ingresso | Uscita |
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