I'm having a difficulity in solving a problem from my class, it's about dynamic programming. The problem is called Waterfall Rock Hit.
We're given the upper left (v1, h1) and lower coordinate (v2, h2) of the rock and we simulate a waterfall and count number of rock hit by the water, imagine the water started falling from a coordinate (x,y), it will fall to (x-1, y) and continue to fall until it hit a rock. when it hit a rock, the water will split to the right and left, and follow the length of the rock, here's the a picture of how the algorithm will work. Simulation Picture.
What we need to watch here, if the rock was hit more than once, the problem also guaranteed there won't any rock stick to each other, and the water will always find a way through any 2 rocks.
Here's a piece of my incomplete code, where i still thinking of the second condition for when the water hit the rock and preventing double count.
int maks=0, n, m, nstone;
struct a{
int v1, v2, h1, h2; //coordinates
bool pass; //passed or not?
}; a arr[5000];
bool acompare(a lhs, a rhs){
return lhs.v1 < rhs.v1; //compare height descending
}
int fall(int x, int y){
if (x == n || y == m || y == -1) //if the water passed the wall
return 0;
else if () //the confusing condition if the water hit the rock
return 1 + fall(x, h1-1) + fall(x, h2+1));
else // if there's nothing below
return fall(x-1, y);
}
int main(){
cin>> n>> m>> nstone; //waterfall size (n*m) and number of stone
for (int i=0; i<nstone; i++){ //read the stone's corner
cin>> arr[i].v1>> arr[i].h1>> arr[i].v2>> arr[i].h2;
arr[i].pass = false;
}
sort(arr, arr+nstone, acompare); //sort the stone's based on height
cin>> start; //read the start point of the water
cout<< fall(start, m)<< endl;
}
testcase sample input : 6 6 3
2 3 2 4
4 2 5 2
5 5 6 5
output :
3
Aucun commentaire:
Enregistrer un commentaire