407623: GYM102861 B Battleship

Battleship is a classic strategy game for two players. Each player places his set of ships in a $$$10 \times 10$$$ grid and then games consist of guessing positions of ships. The actual game rules are not important for this problem, and many variations exist, but here we are interested on a much more basic problem. Given the lists of ships and their positions, your task is to check whether the initial positioning is valid.

The grid rows and columns are numbered from $$$1$$$ to $$$10$$$, and ships are positioned horizontally or vertically, occupying a contiguous sequence of squares of the board. For this problem, a positioning is valid if

• No position is occupied by more than one ship;
• All the ships are totally contained inside the board.

The first line of the input contains an integer $$$N$$$, $$$1 \le N \le 100$$$ the number of ships. Each of the next $$$N$$$ lines contain four integers $$$D$$$, $$$L$$$, $$$R$$$ and $$$C$$$ with $$$D \in \{0, 1\}$$$, $$$1 \le L \le 5$$$ and $$$1 \le R, C \le 10$$$ describing a ship. If $$$D = 0$$$ then the ship is aligned horizontally, and occupy positions $$$(R, C) \ldots (R, C+L-1)$$$. Otherwise the ship is aligned vertically, occupying positions $$$(R, C) \ldots (R+L-1, C)$$$.

Output a single line containing a single character. If the initial positioning of the ships is valid, then write the upper case letter 'Y'; otherwise write the uppercase letter 'N'.

3
0 5 1 1
1 5 2 2
0 1 3 3

Y

2
0 2 1 1
1 1 1 2

N

1
0 2 10 10

N

7
0 3 2 2
1 5 2 9
1 2 3 6
1 1 4 2
0 1 6 6
0 4 8 4
0 2 10 1

Y