#P3519. [Zjoi2014]消棋子
[Zjoi2014]消棋子
[ZJOI2014] 消棋子
题目描述
棋盘有 行、 列,行和列都从 开始编号。棋盘上的格子为空,或放有一枚棋子。每种颜色恰有两枚棋子。
一次操作选择一个空格子及上、下、左、右四个方向中的两个不同方向。从该空格沿各选定方向前进,如果两个方向上都能遇到棋子,且最先遇到的两枚棋子颜色相同,就将这两枚棋子从棋盘上拿走。否则操作无效,棋盘保持原样。
先按顺序执行给出的一串操作,统计成功消去的同色棋子对数。然后将棋盘恢复到初始状态,给出一套能消去最多棋子对的合法操作。
输入格式
第一行有两个整数 。第二行有一个整数 ,表示颜色数。
接下来 行,第 行有四个整数 ,表示颜色 的棋子位于 和 。
接下来一行有一个整数 ,表示给出的操作数。再接下来 行,每行含两个整数 和两个方向字母,分别表示所选格子的行、列和两个方向。字母 U、D、L、R 分别表示上、下、左、右。
输出格式
第一行一个整数,表示给出的操作成功消去的同色棋子对数。
第二行一个整数 ,表示你给出的最优方案的操作数。接下来 行,每行输出空格分隔的行号、列号和两个方向字母,格式与输入操作相同。方案中的操作按顺序从初始棋盘执行。
样例 #1
4 4
4
1 1 1 4
1 2 3 4
1 3 3 2
4 1 2 3
6
2 3 U R
2 1 D R
2 2 L R
2 4 L D
3 1 L R
3 3 L U
2
4
4 3 L U
3 3 L U
3 2 R U
1 2 L R
给出的操作在第 次和第 次各消去一对棋子。样例方案可消去全部四对棋子。
数据范围
,。
| 原赛数据比例 | 附加条件 |
|---|---|
| 另有 |