問題描述：
? ? 。 在韓國戒努， 有一種青蛙
请敦。 每到晚上，這種青蛙會跳躍稻田柏卤，從而踩踏稻子
冬三。 農(nóng)民早上看到被踩踏的稻子， 希望找到造成最大損害的那只青蛙經(jīng)過的路徑
缘缚。 每只青蛙總是沿著一條直線跳躍稻田
勾笆。 且每次跳躍的距離都相同
。 踩到三顆才構成可能路徑
@@@
不同的青蛙的蛙跳步長不同桥滨， 不同青蛙的蛙跳方向可能不同
-------------------------------------------------------------------------------
可能會有多只青蛙從稻田穿越
青蛙每一條都恰好踩在一顆水稻上窝爪，將這顆水稻拍倒
有些水稻可能被多汁青蛙踐踏，?
農(nóng)民看不到青蛙的行走路線
------------------------------------------------------------------------------
程序要求：
1. 在各條青蛙行走路徑種齐媒， 踩踏水稻最多的那一條上蒲每， 有多少顆水稻被踩踏。
@@@@@@@@@@@@@@@@@@@@@@@@@@
解題思路： 枚舉
1.喻括，枚舉每個被踩的稻子作為行走路徑起點（5000個）
2. 對每個七點邀杏， 枚舉行走方向（5000個）
3. 對每個方向枚舉步長（5000種）
4.枚舉步長后要判斷是否每步都踩到水稻
時間5000* 5000* 5000
#########################
思路：
枚舉路徑上的開始兩點
每條青蛙行走路徑中至少有三顆水稻
假設一只青蛙進入稻田后踩到的前兩顆水稻分別是 （x1, y1）`(x2, y2).那么
? ? 青蛙每一跳在x方向上是dx= x2-x1, dy = y2-y1;
? ? (x1-dx, y1-dx)需要落在稻田之外
? ? 當青蛙踩在水稻（x，y）上時唬血， 下一跳踩踏的水稻時（x+dx望蜡，? ? ? ? ? ?y+dx)
? ? ?將路徑上的最后一顆水稻記為（xk, yk), (xk + dx, yk + dy)需要? ? ? ? ? 落在稻田之外。
----------------------------------------
猜測的辦法需要保證：
? ?每條可能的路徑都能被猜測到：
? ? ? ? 從輸入的水稻中任取兩顆
? ? ? ? ? ? ? ? ? ? --》 作為一只青蛙進入稻田后踩到的前兩顆水稻
? ? ? ? ? ? ? ? ? ? ? ?--》 看能否形成一條穿越稻田的行走路徑
拷恨。脖律。。腕侄。小泉。芦疏。。微姊。酸茴。。柒桑。弊决。。魁淳。。与倡。界逛。。纺座。
猜測過程中需要盡快排除錯誤的答案：
猜測（X1,Y1), (X2,Y2)
? ? 當下列條件之一滿足時息拜， 這個猜測就不成立
.1) 青蛙不能經(jīng)過一跳從稻田外跳到（x1,y1)上
2）按照前兩個點確定的步長， 從第一個點出發(fā)净响， 青蛙最多經(jīng)過（maxstep - 1）步少欺， 就跳到了稻田外面
3）maxstep 是當前已經(jīng)找到的最好答案
-----------------------------
選擇合適的數(shù)據(jù)結構
--關于被踩踏的水稻的坐標
1. struct{
int x, y;
}plants[5000]
2. int plantsRows[5000[, plantscol[5000]
#####################
一個有n個元素的數(shù)組， 每次取兩個元素馋贤， 遍歷所有取法
for(int i = 0;i< n-1; i++)
? ? for(int j = i+1; j<n; j++){
? ? ? ? a[i] =...;
? ? ? ? a[j] = ...;
}
------------------------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int r,c,n;
struct PLANT{
? ? int x, y;
};
PLANT plants[5001];
PLANT plant;
int searchPath(PLANT secPlant, int dx, int dy);
======MAIN=====
int main()
{
? ? int i, j, dx, dy px,py, steps, max = 2;
scanf("%d %d",&r, &c);
//行數(shù)的列數(shù)赞别， x方向是上下， y方向是左右
scanf("%d", &n);
for(i = 0; i< n; i++)
? ? scanf("%d %d", &Plants[i].x,&Plants[i].y);
//將水稻按x坐標從小到大排序配乓， x相同按y從小到大排序
sort(plants, plants + n);
for(i = 0; i< n-2; i++)
? ? for(j = i+1; j<n-1; j++){
? ? ? ? dx = plants[j].x - plants[i].x;
? ? ? ? dy = plants[j].y - plants[i].y;
? ? ? ? px = plants[i].x - dx;
? ? ? ? py = plants[i].y - dy;
? ? ? ? if(px <= r && px >=1 && py <=c && py >=1)
? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? // 第一點的前的第一點在田里
? ? ? ? ? ? //說明本次選的兩個點導致的x的方向步長不合理（太蟹绿稀）
? ? ? ? ? ? //取下一個點作為第二個點
? ? ? ? if( plants[i].x + (max - 1) * dx > r)
? ? ? ? ? ? break;????????
? ? ? ? ? ? //x 方向過早越界， 說明本次第二個點不成立
? ? ? ? ? ? // 如果換下一個點作為第二個點犹芹， x方向的步長只會更大崎页， ????????????更不成立
? ? ? ? ? ? //因此應該認為本次第一個點必然不成立，選取下一個點作為 ????????????????第一個點
py = plants[i].y + (max-1)* dy;
if(py> c || py < 1)? continue;
steps = searchPath(plants[j], dx, dy);
if(steps > max) max = steps腰埂；
}
if（max == 2) max = 0;
printf("%d\n", max);
}
bool operator< (const PLANT & p1, const PLANT & p2);
{
? ? ? ? if(p1.x == p2.x)
? ? ? ? ? ? return p1.y < p2.y;
? ? ? ? ? return p1.x< p2.x;
}
int searchPath(PLANT secPlant, int dx, int dy)
{
PLANT plant;
int steps;
plant.x = secPlant.x + dx;
plant.y = secPLant.y + dy;
steps = 2;
while (plant.x <=r && plant.x >=1 && plant.y <=c && plant.y )
{
? ? if(!binary_search(plants, plants +n , plant)){
? ? ? ? //每一步都必須踩到水稻里
? ? ? ? steps = 0;
? ? ? ? break;
}
plant.x += dx;
plant.y += dy;
steps ++;
}
return steps;
}
