アルゴリズムの問題--嫌いなカエル

2819 ワード

テーマゲートhttps://blog.csdn.net/nnnnnnnnnnnny/article/details/51584284
//    ,      
//                 
//            ,        
#include 
#include 
#include 
using namespace std;
int r,c,n;

struct PLANT{
    int x,y;
};  //          
//  debug        
PLANT plants[5001]={{2,1},{6,6},{4,2},{2,5},{2,6},{2,7}
,{3,4},{6,1},{6,2},{6,3},{2,3},{6,4},{6,5},{6,7}}; //    5000   
PLANT plant;

//     
bool operator < (const PLANT &p1, const PLANT &p2){
    if(p1.x == p2.x)
        return p1.y < p2.y;
    return p1.x < p2.x;
}

//    ,         
int searchPath(PLANT secPlant, int dX, int 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<=c && plant.y>=1){
        if(!binary_search(plants, plants+n, plant)){
            //               ,           
            steps = 0;
            break;
        }
        plant.x += dX;
        plant.y += dY;
        steps++;
    }
    return (steps);
}
void input(){
    r = 6;
    c = 7;
    n = 14;
}
int main(){
    int i,j,dX,dY,pX,pY,steps,max = 2;//max          ,          
    /*scanf("%d %d", &r, &c);     //          
    printf("r=%d, c=%d
", r, c); scanf("%d", &n); // printf("n=%d
", n); for(i=0 ; i=1 && pY<=c && pY>=1){ // //printf("(%d, %d)is not the first point of (%d, %d)
", plants[i].x, plants[i].y,plants[j].x,plants[j].y); continue; } // // // dX i , i if(plants[i].x + (max - 1)*dX > r){ //printf("x:(%d, %d)is not the start point of the longest way
", plants[i].x, plants[i].y); break; } pY = plants[i].y + (max - 1)*dY; if(pY > c || pY < 1){ //printf("y:(%d, %d)is not the start point of the longest way
", plants[i].x, plants[i].y); continue; } /*printf("the first point (%d, %d)
", plants[i].x, plants[i].y); printf("the second point (%d, %d)
", plants[j].x, plants[j].y);*/ steps = searchPath(plants[j], dX, dY); // if(steps > max) max = steps; } } if(max == 2) max = 0; printf("%d
", max); }