fork download 
  1. #include<stdio.h>
  2.  
  3. int heightarr[]={1,2,3,4,3,2,3};
  4. int n=7;
  5. //assuming the area of each cell to be 1 each
  6. int A=1;
  7. int volarr[]={0,0,0,0,0,0,0};
  8. void fn(int index,int volpoured)
  9. {
  10. int vcapacity=A*heightarr[index];
  11. if(volpoured+volarr[index]<vcapacity)
  12. {
  13. volarr[index]+=volpoured;
  14. return;
  15. }
  16. if(volpoured+volarr[index]>vcapacity)
  17. {
  18. volpoured-=vcapacity-volarr[index];
  19. volarr[index]=vcapacity;
  20. // if the height of the adjacent left and right columns are both less then equal amt of water overflows on either sides 
  21. if(heightarr[index-1]<=heightarr[index] && heightarr[index+1]<=heightarr[index])
  22. {
  23. fn(index+1,volpoured/2);
  24. fn(index-1,volpoured/2);
  25. }
  26. //if the left column has height greater and left has lesser then entire amt flows to left
  27. else if(heightarr[index-1]>heightarr[index] && heightarr[index+1]<=heightarr[index]&& index!=n-1)
  28. fn(index+1,volpoured);
  29. //if the right column has height lesser and right has height greater then entire amt flows to right
  30. else if(heightarr[index+1]>heightarr[index] && heightarr[index-1]<=heightarr[index] && index!=0)
  31. fn(index-1,volpoured);
  32. //if both left and right have height greater then water overflows at the same index 
  33. else
  34. {
  35. printf("overflow occurs at index %d\n",index);
  36. return;
  37. }
  38.  
  39. }
  40. }
  41. int main()
  42. {
  43. fn(3,19);
  44. int sum=0;
  45. for(int i=0;i<n;i++)
  46. {
  47. printf("%d\t",volarr[i]);
  48. sum+=volarr[i];
  49. }
  50. printf("\namount of water trapped is %d",sum);
  51. }
Success #stdin #stdout 0.02s 2724KB
comments (?)
stdin 
Standard input is empty
stdout 
overflow occurs at index 5
overflow occurs at index 0
1	2	3	4	3	2	0	
amount of water trapped is 15
https://ideone.com/XSJRJ
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!