Poj 1054 The Troublesome Frog / OpenJudge 2812 恼人的青蛙

1.链接地址：

http://poj.org/problem?id=1054

http://bailian.openjudge.cn/practice/2812

2.题目：

3.思路：

枚举，数据量较大，要做优化

首先要判断是否可能为步数最多的，不可能则跳过无需判断

4.代码：

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 using namespace std;

 struct STEP

 {

     int x;

     int y;

 };

 int cmp(const void *a,const void *b)

 {

     STEP step1 = *((STEP *)a);

     STEP step2 = *((STEP *)b);

     if(step1.x == step2.x) return step1.y - step2.y;

     else return step1.x - step2.x;

 }

 int main()

 {

     int i,j;

     int r,c;

     cin>>r>>c;

     int    n;

     cin>>n;

     STEP *steps = new STEP[n];

     for(i = ; i < n; ++i)

     {

         cin>>steps[i].x>>steps[i].y;

     }

     qsort(steps,n,sizeof(STEP),cmp);

     int dx,dy,dx0,dy0,dxk,dyk;

     int max = ;

     int count;

     for(i = ;i < n-; ++i)

     {

         for(j = i + ; j < n; ++j)

         {

             dx = steps[j].x - steps[i].x;

             dy = steps[j].y - steps[i].y;

             dx0 = steps[i].x - dx;

             dy0 = steps[i].y - dy;

             if((dx0 > && dx0 <= r) && (dy0 >  && dy0 <= c)) continue;

             dxk = dx0 + (max + ) * dx;

             dyk = dy0 + (max + ) * dy;

             if(dxk <=  || dxk > r || dyk <=  || dyk > c) continue;

             dxk = steps[j].x + dx;

             dyk = steps[j].y + dy;

             count = ;

             while((dxk > && dxk <= r) && (dyk >  && dyk <= c))

             {

                 STEP step;

                 step.x = dxk;

                 step.y = dyk;

                 if(bsearch(&step,steps,n,sizeof(STEP),cmp) == NULL) break;

                 count++;

                 dxk += dx;

                 dyk += dy;

             }

             if(!((dxk > && dxk <= r) && (dyk >  && dyk <= c)))

             {

                 if(count > max && count > ) max = count;

             }

         }

     }

     cout<<max<<endl;

     delete [] steps;

     return ;

 }