题目是非常经典的搜索+剪枝。题意简言之就是，青蛙需要沿着直线踩着踏点通过田地，并且踏点需要至少为3。问哪条路径青蛙踩坏的作物最多。很好的一个条件是青蛙每次移动都是等间距的。题目需要注意将其排序。
#include <iostream>
using namespace std; #define MAXNUM 5005 typedef struct {
int x, y;
} point_st; point_st points[MAXNUM];
bool Fields[MAXNUM][MAXNUM];
int r, c, n; int comp(const void *a, const void *b) {
point_st *p1 = (point_st *)a;
point_st *p2 = (point_st *)b;
if (p1->x != p2->x)
return p1->x - p2->x;
else
return p1->y - p2->y;
} int calPath(int p1, int p2) {
int x1 = points[p1].x, y1 = points[p1].y;
int x2 = points[p2].x, y2 = points[p2].y;
int nx, ny, cnt = ; while () {
nx = *x2 - x1;
ny = *y2 - y1;
if (nx> && nx<=r && ny> && ny<=c) { // 保持在田地范围内
if (Fields[nx][ny]) {
cnt++;
x1 = x2; y1 = y2;
x2 = nx; y2 = ny;
} else {
return ; // 前面没有踏点了，即此路不通
}
} else {
if (cnt >= )
return cnt;
else
return ; // 踏点不足3，不符合题意
}
}
} int main() {
int i, j, k;
int a, b; while (cin >>r>>c) {
cin >>n; memset(Fields, false, sizeof(Fields)); for (i=; i<n; ++i) {
cin >>points[i].x>>points[i].y;
Fields[points[i].x][points[i].y] = true;
} qsort(points, n, sizeof(point_st), comp);
int sum = ; for (i=; i<n; ++i) {
for (j=i+; j<n; ++j) {
int dx = points[j].x - points[i].x;
if (dx> && ((r-points[i].x)/dx) < sum) // 剪枝1，当前的可移动点数大于sum（sum为当前最大值）
continue;
int dy = points[j].y - points[i].y;
a = points[i].x - dx;
b = points[i].y - dy;
if (a> && a<=r && b> && b<=c) // 剪枝2，该点的前趋点仍然在图中，则证明points[i]点不能作为初始点
continue;
k = calPath(i, j); if (k > sum)
sum = k;
}
} cout <<sum<<endl;
} return ;
}