一, 将C个顶点排序后枚举两点构成直线,然后求最值. ( 排序后枚举,可减少重复枚举 )
二, 我们枚举两点 （i, j ） ，因为我们排序后 （Xi,Yi）都比（Xj,Yj）都小，我们假定 Point(i) 作为跳进稻田路径的第一个点，
这样，我们在之后枚举到相同路径的顶点时，就无需重复计算。
三，跳跃距离（dx,dy）向量相同，我们用 bool vis[5000][5000] 来标记合法点，当未跳出稻田且该点不合法则结束。
解题代码：
View Code
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; #define MAX(a,b) (a)>(b)?(a):(b) const int N = 5010; struct node{ int x, y; void read() { scanf("%d%d",&x,&y); } bool operator < (node tmp) const { if(x == tmp.x) return y < tmp.y; return x < tmp.x; } }p[N]; int n, m, C; bool vis[N][N]; bool legal( int x, int y ) { if( (x >= 1) && (x <= n) && (y >= 1) && (y <= m) ) return true; return false; } void solve() { int ans = -1; sort( p, p+C ); for(int i = 0; i < C; i++) for(int j = i+1; j < C; j++) { int dx = p[j].x-p[i].x; int dy = p[j].y-p[i].y; int step = 2, x = p[j].x, y = p[j].y; // 这里枚举的 I 指的是跳进稻田的入口 if( legal( p[i].x-dx , p[i].y-dy ) ) continue; bool flag = true; while(1) { x += dx; y += dy; if( legal( x, y ) == false ) break; // 直接跳出 if( !vis[x][y] ) // 未跳出且当前无点，不合法 { flag = false; break; } step++; //此时合法且未跳出，才合法 } if( flag ) ans = MAX( ans, step ); } if( ans <= 2 ) ans = 0; printf("%d\n", ans ); } int main() { while( scanf("%d%d",&n,&m) != EOF) { memset(vis, 0, sizeof(vis)); scanf("%d",&C); for(int i = 0; i < C; i++) { p[i].read(); vis[ p[i].x ][ p[i].y ] = true; } solve(); } return 0; }