P3341 [ZJOI2014] Remove Pieces

Remove Pieces is an interesting game. The game is played on an $r \times c$ board. Each cell of the board is either empty or contains a piece of some color. Each color appears exactly twice. In each round, the player can choose an empty cell $(x, y)$ and choose two directions among up, down, left, and right. If, in each of the two chosen directions, there exists a cell containing a piece, and the first piece encountered along each direction has the same color, then we take away those two pieces, and call this a legal move. Otherwise, the move is illegal and the game will not process this move. The goal is to remove as many pieces as possible. Given such a game and a person's sequence of moves, you need to: 1. State how many pieces this person can remove. 2. Provide a sequence of moves that removes the maximum number of pieces.

The first line gives the integers $r$, $c$. The second line gives the integer $n$, the number of different colors. The next $n$ lines, the $i$-th line contains four integers $a_i, b_i, c_i, d_i$, meaning that the two cells of color $i$ are $(a_i, b_i),\ (c_i, d_i)$. Then an integer $m$ follows, the number of this person’s moves. The next $m$ lines each contain two integers and two letters, representing the chosen cell and the two directions. We use $\texttt{UDLR}$ to denote up, down, left, and right, respectively.

The first line outputs how many pieces this person can remove. The second line contains an integer $k$, the number of moves in your sequence. The next $k$ lines each contain two integers and two letters, representing your chosen cell and the two directions.

For all testdata, $1 \leq r, c, n \leq 10^5$, and it is guaranteed that in the answer the number of operations satisfies $0 \leq k \leq 10^6$. Translated by ChatGPT 5