Batalha Naval

면접 대비

시간 제한2초메모리 제한512 MB

요약

10x10 보드에서 배의 방향, 길이, 시작 칸이 주어질 때 모든 배가 보드 안에 들어가고 서로 겹치지 않는지 판정한다.

난이도: 쉬움10점 중 3점
유형: 구현, 시뮬레이션, 배열, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Batalha Naval은 두 명이 하는 고전 전략 게임이다. 각 플레이어는 10 × 10 격자에 자신의 배를 배치하고, 매 라운드마다 상대방 배의 위치를 추측한다. 규칙에는 여러 변형이 있지만 이 문제에서는 그런 규칙이 중요하지 않다. 우리가 관심을 두는 것은 더 기본적인 문제다. 배의 목록과 그 위치가 주어졌을 때, 초기 배치가 유효한지 판별해야 한다.

보드의 행과 열은 1부터 10까지 번호가 매겨지고, 배는 가로 또는 세로 방향으로 놓여 보드의 연속한 칸들을 차지한다. 이 문제에서 배치가 유효하다는 것은 다음을 뜻한다.

어떤 칸도 두 척 이상의 배가 차지하지 않는다.
모든 배가 보드 안에 완전히 들어 있다.

입력

입력의 첫째 줄에는 배의 수를 나타내는 정수 N (1 ≤ N ≤ 100)이 주어진다. 다음 N개 줄 각각에는 배 하나를 나타내는 네 정수 D, L, R, C가 주어지며, D ∈ {0, 1}, 1 ≤ L ≤ 5, 1 ≤ R, C ≤ 10이다. D = 0이면 배는 가로 방향으로 놓여 (R, C), ..., (R, C + L − 1) 칸을 차지한다. 그렇지 않으면 배는 세로 방향으로 놓여 (R, C), ..., (R + L − 1, C) 칸을 차지한다.

출력

한 줄에 문자 하나를 출력한다. 배의 초기 배치가 유효하면 대문자 ‘Y’를 출력하고, 그렇지 않으면 대문자 ‘N’을 출력한다.

예제4

예제 1
입력
```
3
0 5 1 1
1 5 2 2
0 1 3 3
```
예상 출력
```
Y
```
예제 2
입력
```
2
0 2 1 1
1 1 1 2
```
예상 출력
```
N
```
예제 3
입력
```
1
0 2 10 10
```
예상 출력
```
N
```

예제 4

입력

예상 출력