//A <-area of the cell of histogram
// volarr[] <-holds the vol of water already present at particular index
void fn(int index,int volpoured)
{
int vcapacity=A*heightarr[index];
if(volpoured+volarr[index]<vcapacity)
{
volarr[index]+=volpoured;
return;
}
if(volpoured+volarr[index]>vcapacity)
{
volpoured-=vcapacity-volarr[index];
volarr[index]=vcapacity;
// if the height of the adjacent left and right columns are both less then
equal amt of water overflows on either sides
if(heightarr[index-1]<=heightarr[index] &&
heightarr[index+1]<=heightarr[index])
{
fn(index+1,volpoured/2);
fn(index-1,volpoured/2);
}
//if the left column has height greater and left has lesser then entire amt
flows to left
else if(heightarr[index-1]>heightarr[index] &&
heightarr[index+1]<=heightarr[index]&& index!=n-1)
fn(index+1,volpoured);
//if the right column has height lesser and right has height greater then
entire amt flows to right
else if(heightarr[index+1]>heightarr[index] &&
heightarr[index-1]<=heightarr[index] && index!=0)
fn(index-1,volpoured);
//if both left and right have height greater then water overflows at the
same index
else
{
printf("overflow occurs at index %d\n",index);
return;
}
}
// sum of the all elemnts of volarr[] gives the water trapped
On Fri, May 18, 2012 at 10:36 AM, Prem Krishna Chettri
<[email protected]>wrote:
> Algo Dear.. Algo.. implementation Anyone can Do..
>
> Req ppl to share their own algo.. No Someones Code Implementation..
>
> On Fri, May 18, 2012 at 9:54 AM, payal gupta <[email protected]> wrote:
>
>> hope this works..
>> http://ideone.com/XSJRJ
>>
>>
>> On Fri, May 18, 2012 at 8:20 AM, Bhaskar Kushwaha <
>> [email protected]> wrote:
>>
>>> It depends on which column you are pouring the water.
>>> For example
>>> If you choose the shortest column to pour the water then only that
>>> column will be filled with water.
>>>
>>> Please correct me if I am wrong.
>>>
>>>
>>> On Thu, May 17, 2012 at 11:27 AM, Nikhil Agarwal <
>>> [email protected]> wrote:
>>>
>>>> Imagine that you have an histogram stored in an array. Now imagine that
>>>> you can pour water on top of your histogram. Describe an algorithm that
>>>> computes the amount of water that remains trapped among the columns of the
>>>> graph. Clearly on the edges the water would fall off. Use the language or
>>>> the pseudocode you prefer.
>>>>
>>>> --
>>>> Thanks & Regards
>>>> Nikhil Agarwal
>>>> B.Tech. in Computer Science & Engineering
>>>> National Institute Of Technology, Durgapur,India
>>>> http://tech-nikk.blogspot.com
>>>> http://beta.freshersworld.com/communities/nitd
>>>>
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected].
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>>
>>>
>>> --
>>> regards,
>>> Bhaskar Kushwaha
>>> Student
>>> CSE
>>> Third year
>>> M.N.N.I.T. Allahabad
>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
