1、题目
输入
从标准输入设备上读入数据。第一行上两个整数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
2、题目解读
因为要求出最长的路径，所有需要比较全部的路径长度。对于每一条路径，因为步长相等，所有只要确定开始两个被踩的的点就可以求出整条路径。假设前两个点为（x₁,y₁)，(x₂,y₂)，则步长为dx=x₂-x₁,dy=y₂-y₁,需要判断下面三个条件是否都满足。
（1）、之后每个点（xᵢ，yᵢ）=（xᵢ₋₁+dx，yᵢ₋₁+dy）=(x₂+(i-2)*dx,y₂+(i-2)*dy),需要依次判断各个点是否被踩过。
（2）、（x₁-dx,y₁-dy）需要在稻田之外，因为这样才能保证这个（x₁，y₁）这个点是这条最长直线的第一个点，或者是这样才能保证这可能是最长的一条直线。
（3）、将路径上的最后一颗水稻记作（xⱼ，yⱼ）,则（xⱼ+dx，yⱼ+dy）需要在稻田之外。这才能保证最后一个点为稻田的边界。
boolean[][] flag:用来判断是否被青蛙踩过，true表示被踩过，false表示未被踩过
Point[] p:用来记录稻田被踩的点的坐标
题目还要求每条青蛙的行走路径上面至少有三个被踩的点（水稻）否则输出0.
然后就是进行编码，来一一枚举各条直线是否为最长的被踩的直线。
3、代码
import java.awt.*; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; public class 恼人的青蛙 { public static int MAX=5010;//水稻长宽最长为5000 public static int r,c,n,ans=0; public static boolean[][] flag=new boolean[MAX][MAX];//用来判断是否被青蛙踩过，true表示被踩过，false表示未被踩过 public static Point[] p;//用来记录稻田被踩的点的坐标 static boolean Outside(int x1,int y1){//判断是否在农田外true表示在稻田外，false表示在稻田内 return x1 <= 0 || y1 <= 0 || x1 > r || y1 > c; } //判断以a和b为起点的路径是否存在 static boolean count(int a,int b){ int dx=p[b].x-p[a].x;//计算dx int dy=p[b].y-p[a].y;//计算dy //优化条件一：如果不能从稻田外跳到a点，则直接退出 if (!Outside(p[a].x-dx,p[a].y-dy)) return false; //优化条件二：如果青蛙经过MAXSTEPS-1步就会跳出去，那么直接退出 if (p[a].x+ans*dx<=0||p[a].x+ans*dx>r) return false; if (p[a].y+ans*dy<=0||p[a].y+ans*dy>c) return false; int k=2; int x1=p[b].x+dx; int y1=p[b].y+dy; //按照步长将路延伸，并且判断是否被踩而且没有超出稻田的范围 while (!Outside(x1,y1)&&flag[x1][y1]){ k++; x1+=dx; y1+=dy; } //判断是否可以跳出，因为最后一个点应该在稻田外面 if (Outside(x1,y1)&&k>ans) ans=k; return true; } public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String[] input1=bf.readLine().split(" "); r=Integer.parseInt(input1[0]); c=Integer.parseInt(input1[1]); n=Integer.parseInt(bf.readLine().trim());//加trim 是因为输入时后面会带一个空格，否则无法转换成整数 p=new Point[n]; //n行输入，表示n个被青蛙踩踏的点 for (int i=0;i<n;i++){ String[] input2=bf.readLine().split(" "); p[i]=new Point(); p[i].x=Integer.parseInt(input2[0]); p[i].y=Integer.parseInt(input2[1]); flag[p[i].x][p[i].y]=true; } //重写sort排序，先比较点的x，再比较y Arrays.sort(p, new Comparator<Point>() { @Override public int compare(Point o1, Point o2) { if (o1.x==o2.x) return o1.y-o2.y; else return o1.x-o2.x; } }); //或者使用lambda表达式来重写比较方法 /*Arrays.sort(p, (o1, o2) -> { if (o1.x==o2.x) return o1.y-o2.y; else return o1.x-o2.x; });*/ //枚举所有点，一一进行判断 for (int i=0;i<n;i++) for (int j=i+1;j<n;j++){ count(i,j); } if (ans<3) ans=0; System.out.println(ans); } }
