【序言】在大家怀疑的眼光下，我做了一个中午和半个下午、调了一个晚上的题目总算A了！
【原题】
消棋子是一个有趣的游戏。游戏在一个r * c的棋盘上进行。棋盘的每个格
子，要么是空，要么是一种颜色的棋子。同一种颜色的棋子恰好有两个。每一轮，
玩家可以选择一个空格子(x, y)，并选择上下左右四个方向中的两个方向，如果
在这两个方向上均存在有棋子的格子，而且沿着这两个方向上第一个遇到的棋子
颜色相同，那么，我们将这两个棋子拿走，并称之为合法的操作。否则称这个操
作不合法，游戏不会处理这个操作。游戏的目的是消除尽量多的棋子。
给出这样一个游戏和一个人的玩法。你需要：
z 指出此人能消去多少棋子。
z 给出一种能消去最多棋子的方案。
【输入格式】
在输入文件eliminate.in中，第一行给出了整数r, c。第二行给出了整数n，
表示不同颜色数。接下来n行，第i行含4个整数a[i], b[i], c[i], d[i]，表示颜色
为i的两个格子分别是(a[i], b[i]), (c[i], d[i])。然后是一个整数m，表示此人的操
作数。接下来m行，每行有2个整数和2个字母，代表了他选择的格子，以及
两个方向。我们用“UDLR”分别表示上下左右。
【输出格式】
在输出文件eliminate.out中，第一行输出此人能消去多少棋子。第二行含一
个整数k(0 ≤k ≤10
6
)，表示你给出的方案的操作数。接下来k行，每行2个整数和
2个字母，代表你选择的格子以及两个方向。
【样例输入】
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
【样例】
【分析】开始感觉思路还是挺简单的，但是代码写起来真的是越写越长。。。
我的基本思路是用set维护相邻的情况，有点像前几天做的那道Garden。对于每一个横行和每一个竖列分别开一个set，表示这一横行和竖列上的坐标。每次的操作都是基于lower_bound的。
首先考虑读入的那个人。显然这个很简单（代码23行），直接模拟即可。比如我们要消掉这样一对棋子。
设左上角(x1,y1)，右下角(x2,y2)。我们可以把x1所在的set里的y1删掉，把y1所在的set里的x1删掉，对于x2,y2也如此。每次判断一对点中间路线上是否还有棋子并删除点。<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+wum3s7XEu7nKx9fu08UmIzIwNTQwO6Os1vfSqrXEwum3s9autKbU2tPat9bA4MzWwtuhozwvcD4KPHA+z8iw0daxvdPE3Mm+tcS3xcjrttPB0NbQo6zIu7rzw7+0zsTDs/bG5NbQ0ru21LXjoaPPyMm+tfTV4rbUteOjrMi7uvPF0LbP0rvPwtXittS147i9vfzKx7fx09DExLbUtePS8s6qyb6z/cHL1eK21LXjtvjSsr/J0tTJvrP9wcujrM2syrHI67bToaPXotLi0rvPwrXE0rvQqc+4vdqhozwvcD4KPHA+otnEs9K7teO/ycTcu+HI67bTusO8uLTOo6zS8rTL0qrTw2ZsYWe8x8K80rvPwqGjPC9wPgo8cD6i2rK70qrN/LzHzNjF0HgxPXgyus15MT15MrXEx+m/9qGjPC9wPgo8cD6i28/UyLvDtr7ZtcTKxyh4MSx5MSm6zSh4Mix5MinLxNbcuf3IpbXEtdrSu7j2teOho7WrysfXotLi1rvKx7K7ubu1xKOsu7nT0Ch4MSx5Mim6zSh4Mix5MSmhozwvcD4KPHA+otzV4tK7tePX7r/Twcujodei0uKjrGxvd2VyX2JvdW5ky9Gyu7W9tcTIt7vht7W72GVuZCgpo6y1q8rH1NplcmFzZaGiZmluZLXItcTKsbryo6zI57n7w7vT0MzYxdDKubT4vfjIpbXEaXRlcmF0b3K78sr9JiMyMDU0MDuyu7bUo6y74bGstfS1xKGjuNXQtM3quvPO0r7N0rvWsVJFoaM8L3A+CjxwPsi7uvPO0r7Nv6rKvML+s6S1xLX3s8zQ8tauwsPBy6Gj0tG+rdPQtePN/Mi0xMTA77eiyfrBy7TtzvOjrLWryse3tNX9s8zQ8tS9vNPUvbOko6jL5Mi70NDK/bK7yse63Lbgo6mho8Wqtb2688C0o6y007bUMbj2teO1vTO49rXj1Nm1vTW49rXjo6zWrrrztrzKx7Tzyv2+3cHLoaM8L3A+CjxwPtPayse+zb+qyry21MXEoaPOqsHLt72x46OsztLWu8XE1+7TxSYjMjA1NDA7tcTH6b/2oaM8L3A+CjxwPqG+1OzK/b7ds8zQ8qG/PC9wPgo8cD48cHJlIGNsYXNzPQ=="brush:java;">#include
#include
#include
using namespace std; bool f[40005][40005];int x1,y1,x2,y2; int main() { freopen("eliminate.in","w",stdout); srand((int)time(0)); int r=10,c=10; printf("%d %d\n",r,c); int n=5; printf("%d\n",n); for (int i=1;i<=n;i++) { while (1) { x1=rand()%r+1;y1=rand()%c+1;x2=rand()%r+1;y2=rand()%c+1; if (!f[x1][y1]&&!f[x2][y2]&&(x1!=x2||y1!=y2)) break; } printf("%d %d %d %d\n",x1,y1,x2,y2); f[x1][y1]=f[x2][y2]=1; } }
真的要好好感谢我的造数据程序。首先是发现了x1==x2特判的时候有点问题。之后就过了8个点，然后剩下的两个最大的点就一直错误，而且答案相差仅一点点！！然后我只好再次无奈的对拍，大约20分钟后拍出了n==5的错误。
一下是错点图片：
后来才发现，iterator的指针基本每个函数都有，还开了全局变量。这样，Find里的iterator因为执行了一个check过程而有微小的变化。数据真的是太厉害了！
【代码】
#include
#include
#include
#include