/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 700 点
問題文
H 行 W 列のマス目で表されるキャンバスがあり、上から i (1 \leq i \leq H) 行目・左から j (1 \leq j \leq W) 列目のマスを (i, j) と表します。最初、マス (i, j) は s_{i, j}= R のとき赤色で、s_{i, j}= B のとき青色で塗られています。
あなたは「次の 2 つのうち一方を選んで操作すること」を何回でも行うことができます。
操作X 赤色で塗られているマスを 1 つ選び、そのマスと同じ行にあるすべてのマス（自分自身を含む）を白色に塗り替える。
操作Y 赤色で塗られているマスを 1 つ選び、そのマスと同じ列にあるすべてのマス（自分自身を含む）を白色に塗り替える。
最終的に白色で塗られたマスの個数を最大にするような、操作手順の一例を示してください。
制約
- 1 \leq H \leq 2500
- 1 \leq W \leq 2500
- s_{i, j} は
RまたはBである (1 \leq i \leq H, 1 \leq j \leq W) - H, W は整数
入力
入力は以下の形式で標準入力から与えられます。
H W
s_{1, 1}s_{1, 2}s_{1, 3}\cdotss_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3}\cdotss_{2, W}
s_{3, 1}s_{3, 2}s_{3, 3}\cdotss_{3, W}
\vdots
s_{H, 1}s_{H, 2}s_{H, 3}\cdotss_{H, W}
出力
以下の形式で、標準出力に出力してください。
n t_1 r_1 c_1 t_2 r_2 c_2 t_3 r_3 c_3 \vdots t_n r_n c_n
ここで、n は操作を行う回数、t_i, r_i, c_i (1 \leq i \leq n) は「i 回目にはマス (r_i, c_i) を選び操作 t_i を行うこと」を表しています。
t_i は X または Y でなければなりません。
なお、複数通りの答えが考えられる場合は、そのどれを出力しても構いません。
入力例 1
4 4 RBBB BBBB BBBB RBRB
出力例 1
3 X 1 1 Y 4 3 X 4 1
たとえば次のように操作を行うことで、10 個のマスを白色にすることができます。
- まず、マス (1, 1) を選び、操作Xを行う。
- 次に、マス (4, 3) を選び、操作Yを行う。
- 次に、マス (4, 1) を選び、操作Xを行う。
なお、11 個以上のマスを白色にする方法は存在しません。
入力例 2
1 119 BBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBB
出力例 2
4 Y 1 60 Y 1 109 Y 1 46 X 1 11
すべてのマスを白色に塗り替えることができます。
入力例 3
10 10 BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB
出力例 3
0
赤色のマスが 1 つも存在しないため、そもそも操作を行うことができません。
Score: 700 points
Problem Statement
We have a canvas represented as a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top (1 \leq i \leq H) and j-th column from the left (1 \leq j \leq W). Initially, (i, j) is painted red if s_{i, j}= R and blue if s_{i, j}= B.
For any number of times, you can choose one of the two operations below and do it.
Operation X: Choose a square painted red, and repaint all squares in the row containing that square (including itself) white.
Operation Y: Choose a square painted red, and repaint all squares in the column containing that square (including itself) white.
Show one way that maximizes the number of squares painted white in the end.
Constraints
- 1 \leq H \leq 2500
- 1 \leq W \leq 2500
- s_{i, j} is
RorB. (1 \leq i \leq H, 1 \leq j \leq W) - H and W are integers.
Input
Input is given from Standard Input in the following format:
H W
s_{1, 1}s_{1, 2}s_{1, 3}\cdotss_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3}\cdotss_{2, W}
s_{3, 1}s_{3, 2}s_{3, 3}\cdotss_{3, W}
\vdots
s_{H, 1}s_{H, 2}s_{H, 3}\cdotss_{H, W}
Output
Print the following to Standard Output:
n t_1 r_1 c_1 t_2 r_2 c_2 t_3 r_3 c_3 \vdots t_n r_n c_n
Here, n is the number of operations you do, and t_i, r_i, c_i means that your i-th operation is Operation t_i with (r_i, c_i) being chosen, where t_i is X or Y.
If there are multiple possible solutions, you may print any of them.
Sample Input 1
4 4 RBBB BBBB BBBB RBRB
Sample Output 1
3 X 1 1 Y 4 3 X 4 1
Here is one sequence of operations that makes 10 squares white:
- First, do Operation X choosing (1, 1).
- Then, do Operation Y choosing (4, 3).
- Then, do Operation X choosing (4, 1).
There is no way to make 11 or more squares white.
Sample Input 2
1 119 BBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBB
Sample Output 2
4 Y 1 60 Y 1 109 Y 1 46 X 1 11
We can repaint all squares white.
Sample Input 3
10 10 BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB
Sample Output 3
0
Since there is no red square, we cannot do the operations at all.