问题描述：
。 在韩国， 有一种青蛙
。 每到晚上，这种青蛙会跳跃稻田，从而踩踏稻子
。 农民早上看到被踩踏的稻子， 希望找到造成最大损害的那只青蛙经过的路径
。 每只青蛙总是沿着一条直线跳跃稻田
。 且每次跳跃的距离都相同
。 踩到三颗才构成可能路径
@@@
不同的青蛙的蛙跳步长不同， 不同青蛙的蛙跳方向可能不同
-------------------------------------------------------------------------------
可能会有多只青蛙从稻田穿越
青蛙每一条都恰好踩在一颗水稻上，将这颗水稻拍倒
有些水稻可能被多汁青蛙践踏，
农民看不到青蛙的行走路线
------------------------------------------------------------------------------
程序要求：
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) 青蛙不能经过一跳从稻田外跳到（x1,y1)上
2）按照前两个点确定的步长， 从第一个点出发， 青蛙最多经过（maxstep - 1）步， 就跳到了稻田外面
3）maxstep 是当前已经找到的最好答案
-----------------------------
选择合适的数据结构
--关于被踩踏的水稻的坐标
1. struct{
int x, y;
}plants[5000]
2. int plantsRows[5000[, plantscol[5000]
#####################
一个有n个元素的数组， 每次取两个元素， 遍历所有取法
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);
//行数的列数， 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;
}
网友评论