学步园

Description

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.

Input

Sample Input

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

Sample Output

7

Source

解题思路：

        这题一开始自己写的时候，没出来，想的太多了，其实题意很简单只要认真读了几遍后，你就能好好的理解了， 。

         在一个矩阵方格里面，青蛙在里面跳，但是青蛙每一步都是等长的跳，从一个边界外，跳到了另一边的边界外，每跳一次对那个点进行标记。

现在给你很多青蛙跳过后的所标记的所有点，那请你从这些点里面找出一条路径里面出现过的标记点最多。

1、 要考虑的只能是路径里面标记点大于3的路径

2、 是从边界外跳进，并且最后要跳出边界外。

思路：

  首先将所有点按x坐标排序，取任意两点，判断其扩展节点是否在田里，几个剪枝：

1.从后向前搜索，这样可以减少遍历的元素个数。若当前解为ans，则i只需从n遍历到ans+1（j：ans），若i<=ans，则最优值<=ans，此时遍历无意义。

2.开始遍历时，预判当前能否产生比ans更好地解，若不能，直接跳到下一个。

3.根据当前开始遍历的元素和步长判断当前方案是否已经被遍历过

需要注意的是，青蛙必须能够跳出田，否则，即使step再多也不是有效解。

牛人的思路，学习了

代码：

# include<cstdio>
# include<cstring>
# include<iostream>
# include<algorithm>

using namespace std;

struct point
{
int x,y;
};

int r,c,cnt;

point pos[5010];
bool map[5010][5010];

int cmp(point a,point b)
{
if(a.x==b.x)
   return a.y<b.y;
else
   return a.x<b.x;
}
void solve()
{
int i,j,cc,ans=0;
    bool f = true;
int disx,disy,tmpx,tmpy,testx,testy;
sort(pos+1,pos+cnt+1,cmp);
for(i=cnt;i>ans;i--)
{
   for(j=i-1;j>=ans;j--)
   {
    disx=pos[i].x-pos[j].x;
    disy=pos[i].y-pos[j].y;
    tmpx=pos[j].x;
    tmpy=pos[j].y;
    cc=2;
    testx = pos[i].x+disx;
    testy = pos[i].y+disy;
    if((testx>=1&&testx<=r&&testy>=1&&testy<=c))
     continue;
    testx=pos[i].x-ans*disx;
    testy=pos[i].y-ans*disy;
    if (testx<1||testx>r||testy<1||testy>c||map[testx][testy]==0)
     continue;
    f = true;
    while(tmpx-disx>=1 && tmpx-disx<=r && tmpy-disy>=1 && tmpy-disy<=c)
        {
     if(map[tmpx-disx][tmpy-disy])
     {
      tmpx=tmpx-disx;
      tmpy=tmpy-disy;
      cc++;
     }
     else
     {
        f = false;
      break;
     }
    }
    if( cc>ans&&f )
     ans=cc;
   }

}

if( ans < 3 )
   cout<<'0'<<endl;
else
   cout<<ans<<endl;
}

int main(void)
{
    int i;
    cin>>r>>c;
    cin>>cnt;
    memset(map,0,sizeof(map));
    for(i=1;i<=cnt;i++)
        {
            cin>>pos[i].x>>pos[i].y;
            map[pos[i].x][pos[i].y]=1;
        }
    solve();

return 0;
}