原题：http://bailian.openjudge.cn/practice/2812/
描述在韩国，有一种小的青蛙。每到晚上，这种青蛙会跳越稻田，从而踩踏稻子。农民在早上看到被踩踏的稻子，希望找到造成最大损害的那只青蛙经过的路径。每只青蛙总是沿着一条直线跳越稻田，而且每次跳跃的距离都相同。
如下图所示，稻田里的稻子组成一个栅格，每棵稻子位于一个格点上。而青蛙总是从稻田的一侧跳进稻田，然后沿着某条直线穿越稻田，从另一侧跳出去。如下图所示，可能会有多只青蛙从稻田穿越。青蛙的每一跳都恰好踩在一棵水稻上，将这棵水稻拍倒。有些水稻可能被多只青蛙踩踏。当然，农民所见到的是图4中的情形，并看不到图3中的直线，也见不到别人家田里被踩踏的水稻。
请你写一个程序，确定：在一条青蛙行走路径中，最多有多少颗水稻被踩踏。例如，图4的答案是7，因为第6行上全部水稻恰好构成一条青蛙行走路径。
输入从标准输入设备上读入数据。第一行上两个整数R、C，分别表示稻田中水稻的行数和列数，1≤R、C≤5000。第二行是一个整数N，表示被踩踏的水稻数量， 3≤N≤5000。在剩下的N行中，每行有两个整数，分别是一颗被踩踏水稻的行号(1~R)和列号(1~C)，两个整数用一个空格隔开。而且，每棵被踩踏水稻只被列出一次。
输出从标准输出设备上输出一个整数。如果在稻田中存在青蛙行走路径，则输出包含最多水稻的青蛙行走路径中的水稻数量，否则输出0。
样例输入6 714 2 1 6 6 4 2 2 5 2 6 2 7 3 4 6 1 6 2 2 3 6 3 6 4 6 5 6 7 样例输出7解法思路：能想到枚举的起点也是很不容易的（个人觉得），枚举路径上的前两个点。
这道题的关键还在于剪枝，
判断前两点的合法性（能否从外面一步跳到第一个点）有序，并非随机枚举，步长小的优先考虑，所以要排序，这里超级重要，我自己肯定想不到。剪枝，最多也跳不到现在的最大值的就可以直接否定。 1 #include2 #include3 #include4 #include5 using namespace std; 6 bool field[5001][5001]; 7 int N; 8 int R, C; 9 class Plant {10 public:11 int x, y;12 Plant(int inx,int iny):x(inx),y(iny){}13 bool operator> C;37 int N;38 cin >> N;39 for(int i=0;i> x >> y;42 field[x][y] = 1;43 Plants.push_back(Plant(x, y));44 }45 sort(Plants.begin(), Plants.end());46 for(int i=0;i= 1 && beginx = 1 && beginy R)55 break;//x方向过界，出发点不合理56 if (Plants[i].y + (maxjump - 1)*dy > C || Plants[i].y + (maxjump - 1)*dy < 1)57 continue;//y方向过界，重新选择第二个点58 int steps = maxSteps(Plants[j], dx, dy);//这样跳最多能跳的步数59 if (steps > maxjump)60 maxjump = steps;61 }62 if (maxjump == 2)63 maxjump = 0;64 cout