LCC '22 Contest 4 S5 - Nita's Summer Splash
View as PDFNita 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 xsplashes all cells in rowxC xsplashes all cells in columnxG x ysplashes thegrid with the top left corner at row
xcolumny.
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 , which results in
0 0 1
0 1 0
1 0 1
Then splash column , which results in
0 0 0
0 1 1
1 0 0
Then splash row , which results in
0 0 0
0 1 1
0 1 1
Finally, splash the subgrid with a top-left corner at
, which results in
0 0 0
0 0 0
0 0 0
Sample Input 2
2 2
1 0
1 1
Output for Sample Input 2
N
Explanation for Sample Case 2
No matter what Nita and Bruce do, there's no way to convert the entire grid to all s.
Comments