アルゴリズムの問題--嫌いなカエル
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);
}