ACM-讨厌的青蛙

问题描述

        在韩国，有一种小的青蛙。每到晚上，这种青蛙会跳越稻田，从而踩踏稻子。农民在早上看到被踩踏的稻子，希望找到造成最大损害的那只青蛙经过的路径。每只青蛙总是沿着一条直线跳越稻田，而且每次跳跃的距离都相同，如图 8-4 所示。 稻田里的稻子组成一个栅格，每棵稻子位于一个格点上，如图 8-5 所示。而青蛙总是从稻田的一侧跳进稻田，然后沿着某条直线穿越稻田，从另一侧跳出去，如图 8-6 所示。

        青蛙的每一跳都恰好踩在一棵水稻上，将这棵水稻拍倒。可能会有多只青蛙从稻田穿越，有些水稻被多只青蛙踩踏，如图 8-7 所示。当然，农民所见到的是图 8-8 中的情形，看不到图 3 中的直线。

        根据图 8-8，农民能够构造出青蛙穿越稻田时的行走路径，并且只关心那些在穿越稻田时至少踩踏了 3 棵水稻的青蛙。因此，每条青蛙行走路径上至少包括 3 棵被踩踏的水稻。而在一条青蛙行走路径的直线上，也可能会有些被踩踏的水稻不属于该行走路径。在图 8-8 中，格点(2, 1)、 (6, 1)上的水稻可能是同一只青蛙踩踏的，但这条线上只有两棵被踩踏的水稻，因此不能作为一条青蛙行走路径；格点(2, 3)、 (3, 4)、 (6, 6)在同一条直线上，但它们的间距不等，因此不能作为一条青蛙行走路径；格点(2, 1)、 (2, 3)、 (2, 5)、 (2, 7)是一条青蛙行走路径，该路径不包括格点(2, 6)。请你写一个程序，确定在所有的青蛙行路径中，踩踏水稻棵数最多的路径上有多少棵水稻被踩踏。例如，图 8-8 的答案是 7，因为第 6 行上全部水稻恰好构成一条青蛙行走路径。

输入数据

        从标准输入设备上读入数据。第一行上两个整数 R、 C，分别表示稻田中水稻的行数和列数， 1≤R、 C≤5000。第二行是一个整数 N，表示被踩踏的水稻数量， 3≤N≤5000。在剩下的 N 行中，每行有两个整数，分别是一颗被踩踏水稻的行号(1~R)和列号(1~C)，两个整数用一个空格隔开。而且，每棵被踩踏水稻只被列出一次。

输出要求

        从标准输出设备上输出一个整数。如果在稻田中存在青蛙行走路径，则输出包含最多水稻的青蛙行走路径中的水稻数量，否则输出 0。

输入样例

6 7 14 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

解题思路

        这个问题看起来很复杂，其实目的很简单：帮助农民找到为害最大的青蛙。也就是要找到一条穿越稻田的青蛙路径，这个路径上被踩踏的水稻不少于其他任何青蛙路径上被踩踏的水稻数。当然，整个稻田中也可能根本就不存在青蛙路径。问题的关键是：找到穿越稻田的全部青蛙路径。任何一条穿越稻田的青蛙路径 L，至少包括 3 棵被踩踏的水稻。假设其中前两棵被踩踏的水稻分别是(X₁， Y₁)、 (X₂， Y₂)，那么：

令 d_x=X₂-X₁、 d_y=Y₂-Y₁； X₀=X₁-d_x、 Y₀=Y₁- d_y； X₃=X₂ + d_x、 Y₃=Y₂ + d_y(X₀， Y₀)位于稻田之外，青蛙从该位置经一跳后进入稻田、踩踏位置(X₁， Y₁)上的水稻 (X₃， Y₃)位于稻田之内，该位置是 L 上第 3 棵被青蛙踩踏的水稻 X_i=X₀ + i×d_x , Y_i=Y₁ + i×d_y(i>3)，如果(X_i， Y_i)位于稻田之内，则(X_i， Y_i)上的水稻必被青蛙踩踏         根据上述规则，只要知道一条青蛙路径上的前两棵被踩踏的水稻，就可以找到该路径上其他的水稻。为了找到全部的青蛙路径，只要从被踩踏的水稻中，任取两棵水稻(X ₁， Y ₁)、 (X ₂，Y ₂)，判断(X ₁， Y ₁)、 (X ₂， Y ₂)是否能够作为一条青蛙路径上最先被踩踏的两颗水稻。

参考程序

#include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> using namespace std; int r,c,n; struct PLANT { int x,y; }; PLANT plants[5001]; PLANT plant; bool cmp(PLANT plant1,PLANT plant2){ if(plant1.x == plant2.x){ return plant1.y < plant2.y; }else { return plant1.x < plant2.x; } } int searchPath(PLANT secPlant,int dX,int dY){ PLANT plant; int steps = 2; plant.x = secPlant.x + dX; plant.y = secPlant.y + dY; while(plant.x <= r && plant.x >= 1 && plant.y <= c && plant.y >= 1){ if(!binary_search(plants,plants+n,plant,cmp)){//二分查找 steps = 0; break; } plant.x += dX; plant.y += dY; steps++; } return steps; } int main() { int i,j,dX,dY,pX,pY,steps,mmax=2; cin >> r >> c; cin >> n; for(i=0;i<n;i++){ cin >> plants[i].x >> plants[i].y; } sort(plants,plants+n,cmp); for(i=0;i<n-2;i++){ for(j=i+1;j<n-1;j++){ dX = plants[j].x - plants[i].x; dY = plants[j].y - plants[i].y; pX = plants[i].x - dX; pY = plants[i].y - dY; //说明青蛙的第一步在稻田之内 if(pX <=r && pX >= 1 && pY <= c && pY >= 1){ continue; } //优化，当前位置 * 当前最大步数是否超出稻田范围 if(plants[i].x + mmax * dX > r){ break; } pY = plants[i].y + mmax * dY; if(pY > c || pY < 1){ continue; } steps = searchPath(plants[j],dX,dY); if(steps > mmax){ mmax = steps; } } } if(mmax == 2){ mmax = 0; } cout << mmax; return 0; }