问题分析

本题的核心是在给定的稻田中，根据被压平的水稻植株位置，找出青蛙路径中压平植株数量最多的路径。青蛙路径要求至少压平 3 株水稻，且每一跳的长度相同，并且从稻田一侧外部开始，到另一侧外部结束。

方法思路

数据结构与初始化 使用一个二维数组 field 来表示稻田，初始时所有元素为 0，表示未被压平的植株。 读取输入的稻田行数 R、列数 C 和被压平的植株数量 N。 对于每一个被压平的植株位置，在 field 数组中将对应位置设为 1。 遍历所有可能路径 对于每一个被压平的植株 (i, j)，尝试所有可能的跳跃方向和跳跃长度。 跳跃方向包括水平、垂直和对角线方向（四个对角线方向）。 对于每一个方向，从跳跃长度为 1 开始尝试，直到跳跃出稻田边界。 在每次尝试中，沿着跳跃方向检查路径上的植株是否都被压平，并且路径上至少有 3 株被压平的植株。 如果满足条件，则更新最大压平植株数。

输出结果

最后输出最大压平植株数，如果没有找到符合条件的青蛙路径，则输出 0。

代码实现

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define eps 1e-10
#define maxn 5010
using namespace std;
struct pi
{
	int x,y;	
};
pi p[maxn];
int r,c,n;
bool b[maxn][maxn];
int cmp(pi a,pi b)
{
	if(a.x!=b.x)
	return a.x<b.x;
	return a.y<b.y;
}
int step(int x,int y,int dx,int dy)
{
	int sp=2;
	x+=dx;
	y+=dy;
	while(x>0&&x<=r&&y>0&&y<=c)
	{
	    if(b[x][y]==false)return 0;
		x+=dx;
		y+=dy;
		sp++;
	}
	return sp;
}
void slove()
{
	sort(p,p+n,cmp);
	int ans=0,temp;
	int x,y,dy,dx;
	int x0,y0;
	for(int i=0;i<n-1;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			dx=p[j].x-p[i].x;
			dy=p[j].y-p[i].y;
			x=p[j].x;
			y=p[j].y;
			x0=p[i].x-dx;
			y0=p[i].y-dy;
			if(x0>0&&x0<=r&&y0>0&&y0<=c)continue;
			if(p[i].x+ans*dx>r)break;
			if(p[i].y+ans*dy>c||p[i].y+ans*dy<1)continue;
			temp=step(x,y,dx,dy);
			ans=max(temp,ans);
		}
	}
	printf("%d\n",ans>2?ans:0);
}
int main()
{
	freopen("1054.txt","r",stdin);
    	scanf("%d%d",&r,&c);
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&p[i].x,&p[i].y);
		b[p[i].x][p[i].y]=1;
	}
	slove();
	return 0;
}