Bataille navale
Vous cherchez à développer le jeu « Bataille navale ». Au début de la partie, chaque joueur place quelques navires de guerre sur un plateau à des positions spécifiques. Chaque navire occupe une ligne droite allant de à , où la ligne reliant ces coordonnées est toujours perpendiculaire aux bords de la grille.
Dans un premier temps, vous souhaitez valider la grille pour vous assurer que les joueurs ne placent pas leurs navires trop près les uns des autres ou ne les font pas se chevaucher. Chaque navire doit être séparé d’un autre par au moins une case d’eau. En revanche, il est tout à fait autorisé de positionner un navire le long de la bordure sans laisser d’espace d’eau entre la bordure et le navire.
Entrée
La première ligne de l’entrée contient 3 entiers :
•
n — le nombre de navires (1 ≤ n ≤ 20),•
w — la largeur du champ de bataille (1 ≤ w ≤ 1000),•
h — la hauteur du champ de bataille (1 ≤ h ≤ 1000).Les
n lignes suivantes contiennent chacune 4 entiers : et (1 ≤ ≤ ≤ h) (1 ≤ ≤ ≤ w), qui correspondent aux coordonnées de chaque navire.Sortie
Le programme doit afficher
Valid si la grille est valide et Invalid sinon.Exemples
Entrée | Sortie |
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