vendredi 11 mai 2018

Waterfall Rock Hit Counter

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