POJ 1054 The Troublesome Frog （枚举+优化）

POJ 1054 The Troublesome Frog （枚举+优化）

Description

Input

Your program is to read from standard input. The first line contains two integers R and C, respectively the number of rows and columns in your rice paddy, 1 <= R,C <= 5000. The second line contains the single integer N, the number of flattened rice plants, 3 <= N <= 5000. Each of the remaining N lines contains two integers, the row number (1 <= row number <= R) and the column number (1 <= column number <= C) of a flattened rice plant, separated by one blank. Each flattened plant is only listed once.

Output

Your program is to write to standard output. The output contains one line with a single integer, the number of plants flattened along a frog path which did the most damage if there exists at least one frog path, otherwise, 0.

Sample Input

6 7142 16 64 22 52 62 73 46 16 22 36 36 46 56 7

Sample Output

7

题意

青蛙需要沿着直线踩着踏点通过田地，并且踏点需要至少为3。

问哪条路径青蛙踩坏的作物最多，很好的一个条件是青蛙每次移动都是等间距的。

思路

枚举+剪枝

首先对所有踏点按照x坐标大小排序，然后分别用两个变量i j来代表青蛙跳的过程中的前两个点。

则这两个点之间的间距： ​​dx=a[j].x-a[i].x​​​ 、 ​​dy=a[j].y-a[i].y​​

假如用两点的间距计算出i前面一个点不在界内，则重新挑选点进行计算。假如用这两点间距以及已知的最大踩坏作物的数量来计算，当前所允许的最后一个点不在界内，跳出。

否则使用当前间距尝试扩充ans。

AC 代码

#include #include#include#include#include#include#includeusing namespace std;#define MAXN 5010bool G[MAXN][MAXN];int row,col,N;struct node{ int x,y; bool operator<(const node &o) { if(x==o.x)return y0&&x<=row&&y>0&&y<=col) return true; return false;}int solve(){ int ans=2; for(int i=0; irow) //如果试探之后发现青蛙一定会在界外，则剪枝 break; if(a[j].y+(ans-2)*dy>col||a[j].y+(ans-2)*dy<1) continue; if(judge(a[i].x-dx,a[i].y-dy)) //如果前一个点也在范围内，则排除 continue; int t=1; int x=a[j].x,y=a[j].y; while(judge(x,y)&&G[x][y]) //扩充当前点集数目 x+=dx,y+=dy,t++; if(!judge(x+dx,y+dy)) //如果扩充之后青蛙可以正常跳出去，更新ans ans=max(ans,t); } return ans>2?ans:0;}int main(){ while(~scanf("%d%d",&row,&col)) { scanf("%d",&N); memset(G,false,sizeof(G)); for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。