The Troublesome Frog--POJ 1054

时间：2010-09-24 来源：勇泽

1、题目类型：模拟、暴力法。

2、解题思路：（1）根据输入建立跳点的pos[]数组和标识位置的map[][]矩阵；（2）对跳点按照其横坐标进行排序；（3）暴力法遍历排序好的的跳点比较获得最大的步数，时间复杂度为nlog(n)。

3、注意事项：注意青蛙从区域的外面跳入，必须沿着直线方向跳出区域。

4、实现方法:

#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=-1;
    int disx,disy,tmpx,tmpy;
    sort(pos,pos+cnt,cmp);
    for(i=0;i<cnt;i++)
    {
        for(j=i+1;j<cnt;j++)
        {
            disx=pos[j].x-pos[i].x;
            disy=pos[j].y-pos[i].y;
            tmpx=pos[j].x;
            tmpy=pos[j].y;
            CC=2;
            if((pos[i].x-disx>=1&&pos[i].x-disx<=R&&pos[i].y-disy>=1&&pos[i].y-disy<=C))
                continue;
            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
                    goto L;                
            }            
            if(CC>ans)
                ans=CC;
L:
            ;
        }
    }
    
    if(ans<3)
        cout<<'0'<<endl;
    else
        cout<<ans<<endl;
}

int main()
{
    int i;
    cin>>R>>C;
    cin>>cnt;
    memset(map,0,sizeof(map));
    for(i=0;i<cnt;i++)
    {
        cin>>pos[i].x>>pos[i].y;
        map[pos[i].x][pos[i].y]=1;
    }
    Solve();
    return 0;
}