讨厌的青蛙（枚举）

浅浅的花香味﹌ 2022-06-10 12:22 192阅读 0赞

图片来源：[点击打开链接][Link 1]

问题讲解：   
![这里写图片描述][20160604143615070]  
![20160604143625601][]  
![这里写图片描述][20160604143645383]  
![这里写图片描述][20160604143655774]  
![这里写图片描述][20160604143707976]  
![这里写图片描述][20160604143717304]

解题思路:

任意确定两点，作为青蛙跳的前两点，然后判断这两点是否合理：

1. 第一点的前一点还在稻田中，说明步长不合理，重新选第二点；

2. x方向越界，重新选择第一点。（因为x是从小到大排序，第二点不管怎么选步长只会越来越大，所以需要重新选择第一点。）

3. y方向越界，重新选择第二点。

然后枚举满足条件的前两点，用二分查找判断后续的点是否踩踏，计算不同前两点开始的踩踏的数量。

(1) 任何一条穿越稻田的青蛙路径L，至少包括3 棵被踩踏的水稻。假设其中前两棵被踩踏的水稻分别是(X1，Y1)、(X2，Y2)，那么：  
\* 令 dx=X2-X1、dy=Y2-Y1；X0=X1-dx、Y0=Y1- dy；X3=X2 + dx、Y3=Y2 + dy  
\* (X0，Y0)位于稻田之外，青蛙从该位置经一跳后进入稻田、踩踏位置(X1，Y1)上的水稻  
\*(X3，Y3)位于稻田之内，该位置是L 上第3 棵被青蛙踩踏的水稻  
\* Xi=X0 + idx、Yi=Y1 + idy(i3)，如果(Xi，Yi)位于稻田之内，则(Xi，Yi)上的水稻必被青蛙踩踏

(2) 从被踩踏的水稻中选择两棵(X1，Y1)、(X2，Y2)。判断它们是否能够作为一条青蛙路径上最先被踩踏的两颗水稻。(X1，Y1)、(X2，Y2)唯一确定了蛙跳的方向和步长，从(X2，Y2)开始，沿着这个方向和步长在稻田内走。每走一步，判断所到达位置上(X，Y)的水稻是否被踩踏，直到走出稻田为止。

(3) 用一个 PLANT 型的数组plants\[5001\]表示全部被踩踏的水稻  
\*将 plants 中的元素按照行/列序号的升序(或者降序)排列  
\*采用二分法查找 plants 中是否有值为(X，Y)的元素： binary\_search(plants,plants+n,plant);//判断plant是否在plants\[\]中，若在，plant被踩踏，符合条件。

解法1：自定义排序规则（sort）sort(plants,plants+n,paixu);

/*
    6 7
    14
    2 1
    6 6
    4 2
    2 5
    2 6
    2 7
    3 4
    6 1
    6 2
    2 3
    6 3
    6 4
    6 5
    6 7
    */
    #include<iostream>
    #include<algorithm>//sort()和binary_search() 
    using namespace std;
    int r,c,n;//水稻的行列 
    struct PLANT{//描述一棵被踩踏的水稻 
    	int x;
    	int y;//水稻的行号和列号 
    }; 
    PLANT plants[5001];//存储稻谷的位置 
    PLANT plant;//存储临时的点 
    int searchPath(PLANT secPlant,int dX,int dY); //寻找路径
    bool paixu(const PLANT &a,const PLANT &b)//按x从小到大排序，x相同时，按y从小到大排序 
    {
    	if(a.x==b.x) return a.y<b.y;
    	return a.x<b.x;
    }
    
    int main()
    {
    	int i,j,dX,dY,pX,pY,steps,max=2;
    	cin>>r>>c;//稻田的行列，x方向是上下，y方向是左右
    	cin>>n;//被踩踏的稻谷数目
    	for(i=0;i<n;i++) cin>>plants[i].x>>plants[i].y;
    	sort(plants,plants+n,paixu);//将水稻按x坐标从小到大，x相同按y从小到大排序
    	for(i=0;i<n-2;i++)//plants[i]是第一步（点）
    	{
    		for(j=i+1;j<n-1;j++)//plants[j]是第二个点
    		{
    			dX=plants[j].x-plants[i].x;//前两步（点）在x方向的步长
    			dY=plants[j].y-plants[i].y;
    			pX=plants[i].x-dX;//第1点的前一点的步长
    			pY=plants[i].y-dY;
    			//第一点的前一点在稻田里，说明本次选择的第二点导致的x方向的步长不合理，
    			//取下一点作为第二点 
    			if(pX<=r&&pX>=1&&pY<=c&&pY>=1) continue;
    			//x方向过早越界了，说明本次选的第二点不成立
    			//如果换下一个点作为第二点，x方向的补偿只会更大，更不成立；
    			//所以应该认为本次选的第一点必然是不成立的，选择下一点作为第一点再试 
    			if(plants[i].x+(max-1)*dX>r) break;
    			pY=plants[i].y+(max-1)*dY;
    			//y方向过早越界了，应换一个点作为第二点 
    			if(pY>c||pY<1) continue; 
    			steps=searchPath(plants[j],dX,dY);//看看从这两点出发，一共能走几步
    			if(steps>max) max=steps;	 
    		} 
    	} 
    	if(max==2) max=0;//没有一条合适的路径 
    	cout<<max;
    } 
     
     
    int searchPath(PLANT secPlant,int dX,int dY)//判断从secPlant点开始，步长为dX,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>=1&&plant.y<=c)
    	{
    		if(!binary_search(plants,plants+n,plant))//用二分查找判断plant是否在路径中
    		//每一步都必须踩到水稻才合理，否则这就不是一条行走路径 
    		{
    			steps=0;
    			break;
    		}
    		plant.x=plant.x+dX;//下一个点 
    		plant.y=plant.y+dY; 
    		steps++; 
    	}
    	return steps;	
    }

解法2：重载运算符（sort）sort(plants,plants+n);

/*
    6 7
    14
    2 1
    6 6
    4 2
    2 5
    2 6
    2 7
    3 4
    6 1
    6 2
    2 3
    6 3
    6 4
    6 5
    6 7
    */
    #include<iostream>
    #include<algorithm>//sort()和binary_search() 
    using namespace std;
    int r,c,n;//水稻的行列 
    struct PLANT{//描述一棵被踩踏的水稻 
    	int x;
    	int y;//水稻的行号和列号 
    }; 
    PLANT plants[5001];//存储稻谷的位置 
    PLANT plant;//存储临时的点 
    int searchPath(PLANT secPlant,int dX,int dY); //寻找路径
    bool operator < (const PLANT &a,const PLANT &b)//运算符重载 
    {
    	if(a.x==b.x) return a.y<b.y;
    	return a.x<b.x;
    } 
    
    int main()
    {
    	int i,j,dX,dY,pX,pY,steps,max=2;
    	cin>>r>>c;//稻田的行列，x方向是上下，y方向是左右
    	cin>>n;//被踩踏的稻谷数目
    	for(i=0;i<n;i++) cin>>plants[i].x>>plants[i].y;
    	sort(plants,plants+n);//将水稻按x坐标从小到大，x相同按y从小到大排序
    	for(i=0;i<n-2;i++)//plants[i]是第一步（点）
    	{
    		for(j=i+1;j<n-1;j++)//plants[j]是第二个点
    		{
    			dX=plants[j].x-plants[i].x;//前两步（点）在x方向的步长
    			dY=plants[j].y-plants[i].y;
    			pX=plants[i].x-dX;//第1点的前一点的步长
    			pY=plants[i].y-dY;
    			//第一点的前一点在稻田里，说明本次选择的第二点导致的x方向的步长不合理，
    			//取下一点作为第二点 
    			if(pX<=r&&pX>=1&&pY<=c&&pY>=1) continue;
    			//x方向过早越界了，说明本次选的第二点不成立
    			//如果换下一个点作为第二点，x方向的补偿只会更大，更不成立；
    			//所以应该认为本次选的第一点必然是不成立的，选择下一点作为第一点再试 
    			if(plants[i].x+(max-1)*dX>r) break;
    			pY=plants[i].y+(max-1)*dY;
    			//y方向过早越界了，应换一个点作为第二点 
    			if(pY>c||pY<1) continue; 
    			steps=searchPath(plants[j],dX,dY);//看看从这两点出发，一共能走几步
    			if(steps>max) max=steps;	 
    		} 
    	} 
    	if(max==2) max=0;//没有一条合适的路径 
    	cout<<max;
    } 
     
     
    int searchPath(PLANT secPlant,int dX,int dY)//判断从secPlant点开始，步长为dX,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>=1&&plant.y<=c)
    	{
    		if(!binary_search(plants,plants+n,plant))//用二分查找判断plant是否在路径中
    		//每一步都必须踩到水稻才合理，否则这就不是一条行走路径 
    		{
    			steps=0;
    			break;
    		}
    		plant.x=plant.x+dX;//下一个点 
    		plant.y=plant.y+dY; 
    		steps++; 
    	}
    	return steps;	
    }

[Link 1]: http://blog.csdn.net/nnnnnnnnnnnny/article/details/51584284
[20160604143615070]: /images/20220610/2d0775eac24b40b597e349417f4b4ffa.png
[20160604143625601]: /images/20220610/37e74410b47a4c2c83275a598d172828.png
[20160604143645383]: /images/20220610/24d2a3453e3f476da66b54a1ef021943.png
[20160604143655774]: /images/20220610/7fa6be6739a74bae8229fb7e3be3c844.png
[20160604143707976]: /images/20220610/93f44229061648fdb8e9ad6f8d864240.png
[20160604143717304]: /images/20220610/5b2ff884b66d49db876525e8710ff585.png