POJ1054 FrogsPath

Chenglei Si
Sep 8, 2018 · 2 min read

Problem description: the frog can only jump in a straight line. The points that the frog passes, the plant will be damaged. Given a matrix, with some points damaged by frogs, find the path with the most number of plants damaged. A path is formed by at least three points and the step before/after the first/last point must be outside the matrix.

The problem can be solved by enumeration.

First, note that we need a direction to do enumeration. For example, we can sort all the points by their x coordinate (row number), then enumerate all possible first two points. In this way, we are actually going from top to bottom, so the second point we choose should be below the first point (i.e. larger x coordinate). In this way, we can simply use a nested for loop to enumerate all possible first two points.

Another import trick is to cut invalid cases. We can get step size once we choose the first two points, then we can check whether one step before the first point is outside the matrix. Also, we can keep track of the longest path. If the current path is obviously shorter than the stored longest path, we don’t need to continue checking. (Take note of how we implement this in codes.)

Accepted solution:

#include <iostream>
#include <algorithm>
using namespace std;
int row, col, n;struct plant{
int x, y;
};
plant plants[5005];//reload < operator
//how you sort suggests the direction used
//here top to bottom
bool operator < (plant a, plant b){
if(a.x == b.x)
//doesn't matter > or <
//but must specify because binary search needs it
return a.y < b.y;
return a.x < b.x;
}
int searchPath(plant secPoint, int dx, int dy){
int steps = 2;
int px = secPoint.x + dx, py = secPoint.y + dy;
while(px<=row && py>=1 && py<=col){
if(!binary_search(plants, plants+n, plant{px, py})){
return 0;
}
steps++;
px += dx;
py += dy;
}
return steps;
}
int main(){
cin>>row>>col>>n;
//x: row no., y: col no.
//step means #plants on the way
int dx, dy, px, py, MAXSTEP=2, steps;
for(int i=0; i<n; i++){
cin>>plants[i].x>>plants[i].y;
}
sort(plants, plants+n);
//need at least three points to form a path!
for(int i=0; i<n-2; i++){
for(int j=i+1; j<n-1; j++){
dx = plants[j].x - plants[i].x;
dy = plants[j].y - plants[i].y;

//check the first point's previous step
px = plants[i].x - dx;
py = plants[i].y - dy;

//not outside the field, choose another second point
if(px>=1 && px<=row && py>=1 && py<=col)
continue;

//first point's x too big
//if no improvement possible, just cut it
//next secPoint will have even bigger dx
if(plants[i].x + MAXSTEP*dx > row)
break;

py = plants[i].y + MAXSTEP*dy;
if(py<1 || py>col)
continue;

steps = searchPath(plants[j], dx, dy);
MAXSTEP = max(steps, MAXSTEP);
//if(steps>0) MAXSTEP = steps;
}
}
if(MAXSTEP==2)
MAXSTEP = 0;
cout<<MAXSTEP<<endl;
}

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade