1054(枚举)

1054:The Troublesome Frog

总时间限制:

5000ms

内存限制:

100000kB

描述

In Korea, the naughtiness of the cheonggaeguri, a small frog, is legendary. This is a well-deserved reputation, because the frogs jump through your rice paddy at night, flattening rice plants. In the morning, after noting which plants have been flattened, you want to identify the path of the frog which did the most damage. A frog always jumps through the paddy in a straight line, with every hop the same length:

Your rice paddy has plants arranged on the intersection points of a grid as shown in Figure-1, and the troublesome frogs hop completely through your paddy, starting outside the paddy on one side and ending outside the paddy on the other side as shown in Figure-2:

Many frogs can jump through the paddy, hopping from rice plant to rice plant. Every hop lands on a plant and flattens it, as in Figure-3. Note that some plants may be landed on by more than one frog during the night. Of course, you can not see the lines showing the paths of the frogs or any of their hops outside of your paddy ?for the situation in Figure-3, what you can see is shown in Figure-4:

From Figure-4, you can reconstruct all the possible paths which the frogs may have followed across your paddy. You are only interested in frogs which have landed on at least 3 of your rice plants in their voyage through the paddy. Such a path is said to be a frog path. In this case, that means that the three paths shown in Figure-3 are frog paths (there are also other possible frog paths). The vertical path down column 1 might have been a frog path with hop length 4 except there are only 2 plants flattened so we are not interested; and the diagonal path including the plants on row 2 col. 3, row 3 col. 4, and row 6 col. 7 has three flat plants but there is no regular hop length which could have spaced the hops in this way while still landing on at least 3 plants, and hence it is not a frog path. Note also that along the line a frog path follows there may be additional flattened plants which do not need to be landed on by that path (see the plant at (2, 6) on the horizontal path across row 2 in Figure-4), and in fact some flattened plants may not be explained by any frog path at all.

Your task is to write a program to determine the maximum number of landings in any single frog path (where the maximum is taken over all possible frog paths). In Figure-4 the answer is 7, obtained from the frog path across row 6.

输入

Your program is to read from standard input. The first line contains two integers R and C, respectively the number of rows and columns in your rice paddy, 1 <= R,C <= 5000. The second line contains the single integer N, the number of flattened rice plants, 3 <= N <= 5000. Each of the remaining N lines contains two integers, the row number (1 <= row number <= R) and the column number (1 <= column number <= C) of a flattened rice plant, separated by one blank. Each flattened plant is only listed once.

输出

Your program is to write to standard output. The output contains one line with a single integer, the number of plants flattened along a frog path which did the most damage if there exists at least one frog path, otherwise, 0.

样例输入

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

样例输出

7

 翻译：

问题描述：在韩国，有一种小的青蛙。每到晚上，这种青蛙会跳越稻田，从而踩踏稻子。农民在早上看到被踩踏的稻子，希望找到造成最大损害的那只青蛙经过的路径。
每只青蛙总是沿着一条直线跳越稻田，而且每次跳跃的距离都相同。
不同的青蛙有不同的跳跃距离，不同的跳跃方向。

如下图所示，稻田里的稻子组成一个栅格，每棵稻子位于一个格点上。而青蛙总是从稻田的一侧跳进稻田，然后沿着某条直线穿越稻田，从另一侧跳出去

如下图所示，可能会有多只青蛙从稻田穿越。青蛙的每一跳都恰好踩在一棵水稻上，将这棵水稻拍倒。有些水稻可能被多只青蛙踩踏。当然，农民所见到的是图4中的情形，并看不到图3中的直线，也见不到别人家田里被踩踏的水稻。

根据图4，农民能够构造出青蛙穿越稻田时的行走路径，并且只关心那些在穿越稻田时至少踩踏了3棵水稻的青蛙。因此，每条青蛙行走路径上至少包括3棵被踩踏的水稻。而在一条青蛙行走路径的直线上，也可能会有些被踩踏的水稻不属于该行走路径
①不是一条行走路径：只有两棵被踩踏的水稻
②是一条行走路径，但不包括（2，6）上的水道
③不是一条行走路径：虽然有3棵被踩踏的水稻，但这三棵水稻之间的距离间隔不相等
 问，给定一块被踩坏的稻田，求可能的最长的蛙路上被踩坏的作物的数目。
例如，图4的答案是7，因为第6行上全部水稻恰好构成一条青蛙行走路径

输入：

第一行整数R和C，稻田的行数和列数
第二行整数N，表示被踩坏的作物总数。
后续N行，每行两个整数i,j为被 踩坏的作物的行和列的位置: 1<=i<=R, 1<=j<=C。
每个被踩坏的作物只出现一次。

输出：

单个整数
 -- 表示最长可能蛙路上踩坏的作物数目

 

问题分析：

1.在给出的n个点中找出一些点的序列来使得每一个点相对于上一个点的坐标都是一个相同的常量
2.“第一个点减去这个常量”和“最后一个点加上这个常量”后均落在方格的外面。

3.先对这些点按坐标排序

4.然后依次循环出要求得序列中的第一个和第二个点，这样就知道后一个点相对于前一个点的坐标

是多少了

5.依次用第二个点加上这个坐标求出第三个点

6.第三个点加上这个坐标求出第四个点等等

7.判断求出来的第三四个点是否在给定的点内

8.由于每个点的上一个点或下一个点最多只能有n种选择,故一个短最多属于n条不同的路

9.对于某个确定的点来说，它的所有可能的下一个需要判断的点至多有n个。这样因为判断一个点在不在给定的点内只需要O(1)的复杂度，所以只需要O(n2)的时间就可以得出问题的解答。
10.由于这个算法需要一个r*c的表来保存点在方格中的存在状态，故空间复杂度为O(n2)。

11.二分查找

函数名: bsearch
功 能: 二分法搜索
用 法: void *bsearch(const void *key, const void *base, size_t nelem, size_t width, int(*fcmp)(const void *, const *));
语法:
#include <stdlib.h> void *bsearch( const void *key, const void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) ); 
参数：第一个：要查找的关键字。第二个：要查找的数组。第三个：指定数组中元素的数目。第四个：每个元素的长度（以字符为单位）。第五个：指向比较函数的指针。
功能： 函数用折半查找法在从数组元素buf[0]到buf[num-1] 匹配参数key。如果函数compare 的第一个参数小于第二个参数，返回负值；如果等于返回零值；如果大于返回正值。数组buf 中的元素应以升序排列。函数bsearch()的返回值是指向匹配项，如果没有发现匹配项，返回NULL

 

 

解决方案一：G++

 

 

#include<cstdio>
#include<cstdlib>
using namespace std ;
int r,c,n ;
struct PLANT{
 int x,y ;
};
PLANT plants[5001] ;
PLANT plant ;
int myCompare(const void*x,const void*y)
{    //按照x值由小到大排序
    //x相同时,按照y值由小到大到排列
    PLANT *a,*b;
    a=(PLANT*)x;
    b=(PLANT*)y;
    if(a->x==b->x) return (a->y-b->y) ;
    return a->x-b->x ;
}
int searchPath(PLANT secPlant,int dx,int dy)
{  //从secPlant点开始，步长为dx,dy,最多能走几步
    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>=1)
    {
        if(!bsearch(&plant,plants,n,sizeof(PLANT),myCompare))//调用二分查找
        { //每一步必须踩到水稻
           steps = 0 ;
           break ;
        }
       plant.x += dx ;
       plant.y += dy ;
         steps++ ;
    }

   return steps ;
}
int main()
{
 int i,j,dX,dY,pX,pY,steps,max=2;
 scanf("%d%d",&r,&c);//稻田的长和宽
 scanf("%d",&n);//共有多少水稻被踩踏
 for(i=0;i<n;i++)
  scanf("%d%d",&plants[i].x,&plants[i].y) ;
  qsort(plants,n,sizeof(PLANT),myCompare) ;
  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 ;
   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 ;//第一点的前一点还在稻田里,说明本次选的第二点不合理
                    //再选择另外的点在作为第二个点
   if(plants[j].x+(max-1)*dX>r)
       break ; //x方向过早越界,第二点选择不成立
    //如果继续选择下一个点作为第二点,x步长方面的增长
    //只会更大,所以果断要换第一个点
    pY = plants[j].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) ;
   return 0 ;
}

 

解决方案二：Java   

package dsa;

import java.util.Scanner;

public class Demo14 {
  int r,c,n;
  Plant plants[] = new Plant[5001];
  public static void main(String[] args) {
	new Demo14().test() ;
  }
	public void test()
	{
		Scanner sc = new Scanner(System.in);
		int i,j,dX,dY,pX,pY,steps,max=2; 
		r = sc.nextInt() ;
		c = sc.nextInt() ;
		n = sc.nextInt() ;
		for(i=0;i<n;i++)
		{
			plants[i] = new Plant() ;
			plants[i].x = sc.nextInt() ;
			plants[i].y = sc.nextInt() ;
		}
	 Qsort() ;
//	 for(i=0;i<n;i++)
//	 {
//		 System.out.println(plants[i].x+"-----"+plants[i].y);
//	 }
		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 ;
			  
			  if(plants[j].x+(max-1)*dX>r)
			       break ; 
			   
			   pY = plants[j].y + (max-1)*dY ;
			     if(pY>c||pY<1)
			        continue ;
			  
			  steps = searchPath(plants[j],dX,dY) ;
			  //  System.out.println(steps) ;
			    if(steps>max) max = steps ;
			}
	}
		if(max==2) max = 0 ;
		System.out.println(max);
	}
	public int searchPath(Plant secPlant,int dX,int dY)
	{  //从secPlant点开始，步长为dx,dy,最多能走几步
	    int steps ;
	    Plant plant = new Plant();
	    plant.x = secPlant.x + dX ;
	    plant.y = secPlant.y + dY ;
	    steps = 2 ;
	    boolean b ;
	    while(plant.x<=r&&plant.x>=1&&plant.y<=c&&plant.y>=1)
	    {   
	         b 	= bsearch(plant);
	    	//System.out.println(b) ;
	        if(!b)
	        { //每一步必须踩到水稻
	           steps = 0 ;
	           break ;
	        }
	       plant.x += dX ;
	       plant.y += dY ;
	         steps++ ;
	    }
	    
	   // System.out.println(steps) ;
	    return steps ;
	    
	}
	/**
	 * 二分查找
	 */
	public boolean bsearch(Plant plant)
	{  
		int low = 0;
		int high = n-1 ;
		int mid ;
		//System.out.println("开始二分查找") ;
		while(low<=high)
		{
		mid = (low+high)/2 ;
		 if(plant.x==plants[mid].x)
		 { 
			 if(plant.y==plants[mid].y)
			 {
			 return true ;
			 }else if(plant.y<plants[mid].y) high = mid -1 ;
			 else  low = mid +1 ;
		 }else if(plant.x<plants[mid].x) high = mid -1 ;
		 else low = mid +1 ;
		}
		return false ;
	}
	public void Qsort()
	{
		int i,j;
		for(i=0;i<n;i++)
			for(j=i+1;j<n;j++)
			{
			if(	plants[i].x==plants[j].x)
			{
				if(plants[i].y>plants[j].y)
				{
					Plant temp = new Plant();
					temp = plants[i] ;
				    plants[i] =	plants[j] ;
				    plants[j] = temp ;
				}
			}
			if(	plants[i].x>plants[j].x)
			{   
				Plant temp = new Plant();
				temp = plants[i] ;
			    plants[i] =	plants[j] ;
			    plants[j] = temp ;
			}
		}
	//	System.out.println("排序成功") ;
	}
	class Plant{
		int x ;
		int y ;
	}
}

因为java代码中的函数都是自己写的，所以有点复杂，不过还是强免ac了。哈哈！