同样是《算法基础与在线实践》上的百练习题。先上例题：

题目肯定是枚举相关，稍加思考就可以得到一个解决思路（笨比的我想了一天半）：找到任意不相同的两点，当这两点是青蛙进入稻田中先踩的点时，根据两点确定一条直线找到方向和单步步长，进而找到这条直线在稻田上的所有点，再依次判断所有点是否是被踩过的存在的点。如果直线上所有点都满足，就得到了一条合理的青蛙的运动轨迹。

解决思路分析与代码实现

最开始我的思路是开一个[5000][5000]的数组，枚举所有两个点的组合，先判断两点是否都存在（即被踩过），如果被踩过的话再去判断直线是否满足情况。显而易见这种方式时间复杂度太高。于是我将思路优化，从开始的“枚举所有两个点的组合”，变为“枚举所有存在的两个点的组合”。这里是很不相同的：前者是判断在5000*5000的地图上所有点的组合，而后者只考虑被记录的存在的点的组合。具体的操作，我没有抛弃这个5k*5k的数组而去选择一个结构体一维数组来储存。但我在二维数组上改变了原先对于（i，j）点就标记mapmap[i][j]为1的策略（mapmap是数组名），而是选择了将点存放在mapmap[i][x]中，令mapmap[i][x]=j。如下代码：

int tempmapx=0,tempmapy=0;int maxhang=0;for (int i = 1; i <= total; i++){scanf("%d %d",&tempmapx,&tempmapy);mapmap[tempmapx][0]++;mapmap[tempmapx][mapmap[tempmapx][0]]=tempmapy;if(tempmapx>maxhang){maxhang=tempmapx;}}

在mapmap[i][0]中储存第i行有多少个点，同时以i作为数组下标索引存储。通过mapmap[i][0]作为数量值，我们可以遍历第i行的所有点的存储数据。尽管在行内他们是无序的，但是行与行之间是有序的。比如对于测试数据：

经过输入储存后，是这样的

对于一个二维数组mapmap，我们的储存策略是将点的纵坐标存放到其横坐标行，但不排序。这样做有一个好处就是我们可以一次定位到想要找的点的所在行，然后用较少的时间找到该点。可以节省判断某点是否存在的时间。

我们需要枚举两个不同的点，然后依据这两点的方向和步长找到所有在地图上的点。比如第一组点(2,1),(6,6)，我们将第一个点作为起始点，得到的单步步长就是stepx=6-2=4，stepy=6-1=5。此时只要在第二个点上加上横纵步长，就可以得到下一个点的坐标为(10,11)。

如何枚举两个不同的点可以用for循环来找到：每行包含点的数量都存放在了该行内[0]的位置。每层for循环的约束条件就是该值。如下：

for(int i=1;i<=maxhang;i++)//寻找第一个点（直线的起始点）{if(mapmap[i][0]!=0)//如果该行是有点存在的{for(int j=1;j<=mapmap[i][0];j++)//枚举该行内所有点，找到第一个坐标点(i,mapmap[i][j]){for(int a=i;a<=maxhang;a++)//寻找第二个点{if(mapmap[a][0]!=0)//如果该行是有点存在的{int b=j+1;if(a!=i){b=1;} //如果两点是在同一行，寻找第二个点应该从起始点的下一个点开始找。//如果两点并不在同一行，寻找第二个点应该从当前行第一个点开始找。for(;b<=mapmap[a][0];b++)//找到第二个坐标点(a,mapmap[a][b]){int stepx=a-i;//行步长int stepy=mapmap[a][b]-mapmap[i][j];//列步长int tempx;int tempy;//tempx，tempy作为一个暂时的点去遍历寻找是否存在int templong=2;//目前正在判断的这条直线的长度//判断点是否满足条件部分//-------------------------}}}}}}

接下来是判断点是否存在。不过在此之前，我们可以对代码进行优化。此时我们能确定直线上的所有点应该落在什么地方，但不是所有的情况我们都需要去考虑，去逐个验证点是否真的在那里。如果直线上所有的点加起来，数量也并没有超过我们当前已经确认的最大值，那么我们还判断他做什么？直接跳过！所以在找点之前，我们可以加上这段代码：

if(i+totlong*stepx>hang || i+totlong*stepx<=0){ continue;}if(mapmap[i][j]+totlong*stepy>lie || mapmap[i][j]+totlong*stepy<=0){continue;}

如果点是比目前最大值totlong要多的，那么即使只是多一个，这条直线的第totlong+1个点也一定是在地图范围（hang*lie）中的，而不可能出界。如果出界的话，别想了，直接下一位！

做完这一步之后，我们再来判断点的存在情况。我的方法是按照当前步长方向，一步一步走。因为每行的所有点都被我们存放在了同一行，那么我们就可以根据要找的这个点的行数去找到那一行的所有点。如果找到了，这个点是存在的，那么让(tempx,tempy)再走一步到下一个点，直到出界为止；如果这个点不存在，这种情况不可行，那么我们需要再另外枚举两个点判断。

但即使我们枚举的这条直线一直走出界了，他一定就满足条件吗？文章开头我们的思路就有说，我们找到的两个点是且一定是最开始走的两个点。也就是找一号点和二号点：

对于这两种情况，我们可以在开始判断直线上每一个点是否存在前，先判断这条直线反方向上还是否有点可能存在。如果这个点在地图里面，那么这种情况我们可以直接跳过。因为这说明要么我们选取的两个点不是起始点和第二点；要么说明我们选取的起始点不满足情况。这样不仅避免了重复计算已经处理过的直线，更避免了将并不满足条件的情况计算进去的bug。

现在可以上程序总代码了：

#include<iostream>#include<list>#include<algorithm>#include<vector>#include<map>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>using namespace std;int mapmap[5005][5005]={0};int main(){int hang = 0, lie = 0,total=0;scanf("%d %d %d", &hang, &lie,&total);int tempmapx=0,tempmapy=0;int maxhang=0;for (int i = 1; i <= total; i++){scanf("%d %d",&tempmapx,&tempmapy);mapmap[tempmapx][0]++;mapmap[tempmapx][mapmap[tempmapx][0]]=tempmapy;if(tempmapx>maxhang){maxhang=tempmapx;}}int totlong = 0;//储存最长的线for(int i=1;i<=maxhang;i++)//寻找第一个点（直线的起始点）{if(mapmap[i][0]!=0)//如果该行是有点存在的{for(int j=1;j<=mapmap[i][0];j++)//枚举该行内所有点，找到第一个坐标点(i,mapmap[i][j]){for(int a=i;a<=maxhang;a++)//寻找第二个点{if(mapmap[a][0]!=0)//如果该行是有点存在的{int b=j+1;if(a!=i){b=1;}//如果两点是在同一行，寻找第二个点应该从起始点的下一个点开始找。//如果两点并不在同一行，寻找第二个点应该从当前行第一个点开始找。for(;b<=mapmap[a][0];b++)//找到第二个坐标点(a,mapmap[a][b]){int stepx=a-i;//行步长int stepy=mapmap[a][b]-mapmap[i][j];//列步长int tempx=i-stepx;int tempy=mapmap[i][j]-stepy;//tempx，tempy作为一个暂时的点去遍历寻找是否存在int templong=2;//目前正在判断的这条直线的长度if(tempx>=1 && tempx<=hang && tempy>=1 && tempy<=lie){continue;}//如果直线反方向前一个点是可能存在的，那么就要排除此情况if(i+totlong*stepx>hang || i+totlong*stepx<=0){continue;}if(mapmap[i][j]+totlong*stepy>lie || mapmap[i][j]+totlong*stepy<=0){continue;}//当前直线长度比已经记录的最大值要小，故不需继续判断tempx=a+stepx;tempy=mapmap[a][b]+stepy;//开始判断直线上所有点while(tempx>=1 && tempx<=hang && tempy>=1 && tempy<=lie)//判断(tempx,tempy)是否存在{int flag=0;//用flag来记录是否找到点for(int aa=1;aa<=mapmap[tempx][0];aa++)//在该行内查找{if(mapmap[tempx][aa]==tempy)//存在{flag=1;templong++;//总长度+1tempx+=stepx;tempy+=stepy;//判断下一个点break;}}if(flag==0)//没找到，退出循环{goto B;}}if(templong>totlong)//当前情况要比已经记录的要大，更新数据{totlong=templong;}B:;}}}}}}if(totlong<3)//根据题意，小于3的情况要被排除{totlong=0;}printf("%d\n", totlong);return 0;}

感觉自己的方法好笨。。用最原始的方法费最大的气力解决最简单的问题。。。不过总算是解决了。。。还是需要多学习多磨练啊！