Batalha Naval
Está a desenvolver o jogo “Batalha Naval”. No início deste jogo, cada jogador coloca alguns navios em determinadas posições no tabuleiro. Cada navio estende-se numa linha reta de até , e a linha que une estes pontos é sempre perpendicular às bordas da grelha.
Como primeiro passo, pretende validar a grelha para garantir que os jogadores não coloquem os navios demasiado próximos uns dos outros ou até mesmo se sobreponham. Cada navio precisa de pelo menos uma célula de água que o separe de qualquer outro navio. É perfeitamente aceitável colocar navios encostados às margens do tabuleiro sem necessitar de espaço de água adicional.
Input
A primeira linha de entrada contém 3 inteiros:
n - o número de navios (1 ≤ n ≤ 20), w - a largura do campo de batalha (1 ≤ w ≤ 1000) e h - a altura do campo de batalha (1 ≤ h ≤ 1000).As
n linhas seguintes contêm 4 inteiros - e (1 ≤ ≤ ≤ h) (1 ≤ ≤ ≤ w), que representam as coordenadas de cada navio.Output
O programa deve imprimir
Valid se a grelha for válida e Invalid caso contrário.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