同样是《算法基础与在线实践》上的百练习题。先上例题:
题目肯定是枚举相关,稍加思考就可以得到一个解决思路(笨比的我想了一天半):找到任意不相同的两点,当这两点是青蛙进入稻田中先踩的点时,根据两点确定一条直线找到方向和单步步长,进而找到这条直线在稻田上的所有点,再依次判断所有点是否是被踩过的存在的点。如果直线上所有点都满足,就得到了一条合理的青蛙的运动轨迹。
解决思路分析与代码实现
最开始我的思路是开一个[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;}
感觉自己的方法好笨。。用最原始的方法费最大的气力解决最简单的问题。。。不过总算是解决了。。。还是需要多学习多磨练啊!