Nita and Bruce are making a splash at the beach! With so many waves, Nita wants to make sure that the beach is safe for everyone to swim in.
Currently, the beach is a by grid with the water level in each cell being either or . Whenever a cell of the grid is splashed, the water level at that cell changes to if it was or to if it was .
Nita wants to calm the entire area of the beach to level , but she can only perform two types of operations:
- Rupture: Nita splashes all the cells in an entire row or column.
- Bear Paws: Bruce splashes any by subgrid of the beach.
Help Nita and Bruce to convert the water level of every cell of the beach to 0
!
Input Specification
First line: and (the height and width of the beach respectively).
An grid of s and s follows, describing the initial state of the beach.
Output Specification
There are two parts for the output:
Part 1: If it is solvable, print Y
. Otherwise, print N
. (Producing a correct answer for Part 1 in any subtask earns you 75% of the marks for that subtask).
Part 2: If it is solvable, print an integer stating the number of operations in your proposed solution.
On the next lines, list the operations you used to solve the puzzle. More specifically,
R x
splashes all cells in rowx
C x
splashes all cells in columnx
G x y
splashes the grid with the top left corner at rowx
columny
.
If multiple valid solutions exist, any one of them will be accepted. does not need to be minimal but should not exceed .
Constraints
In all test cases,
Subtask 1 [20%]
Subtask 4 [80%]
No additional constraints.
Remember: for all subtasks, you will be awarded 75% of the available points for producing a correct answer for Part 1 of the output specification, regardless of your output for Part 2.
Sample Input 1
3 3
1 0 1
1 1 0
0 0 1
Sample Output 1
Y
4
C 1
C 3
R 3
G 2 2
Explanation for Sample Case 1
Nita splashes column , leaving
0 0 1
0 1 0
1 0 1
Then splash column , leaving
0 0 0
0 1 1
1 0 0
Then splash row , leaving
0 0 0
0 1 1
0 1 1
Finally, splash the subgrid with a top-left corner at , leaving
0 0 0
0 0 0
0 0 0
Note: if you had simply outputted Y
without listing the operations, you would have earned 75% of the points.
Comments