Sea Battle
Estás tratando de desarrollar el juego “Sea Battle”. Al inicio de la partida, cada jugador coloca varios barcos de batalla en el tablero, ubicándolos en puntos concretos. Cada barco se extiende en línea recta desde hasta , donde la línea que conecta esas coordenadas siempre es perpendicular a los bordes de la cuadrícula.
Como primer paso, quieres validar el tablero para asegurarte de que los usuarios no pongan los barcos demasiado cerca unos de otros, ni que se crucen entre sí. Cada barco debe tener al menos una celda de agua que lo separe de cualquier otro. Sin embargo, está permitido ubicar un barco justo al lado del borde sin dejar un espacio adicional entre el barco y el borde.
Input
La primera línea de la entrada contiene 3 enteros:
n (el número de barcos, 1 ≤ n ≤ 20), w (el ancho del campo de batalla, 1 ≤ w ≤ 1000) y h (la altura del campo de batalla, 1 ≤ h ≤ 1000).Las siguientes n líneas contienen 4 enteros: y (1 ≤ ≤ ≤ h) (1 ≤ ≤ ≤ w) que representan las coordenadas de cada barco.
Output
El programa debe imprimir
Valid si el tablero es válido o Invalid en caso contrario.Examples
Input | Output |
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