Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.Thanks Marcos for contributing this image!

C++:
01 int water(int A[], int n, int start, int end)
02 {
03     if(start>=end1)
04         return 0;
05     vector<int> maxdex;
06     int max=A[start];
07     maxdex.push_back(start);
08     for(int i=start+1;i<=end;i++){
09         if(A[i]>max){
10             maxdex.clear();
11             maxdex.push_back(i);
12             max=A[i];
13         }
14         else if(A[i]==max){
15             maxdex.push_back(i);
16         }
17     }
18     if(maxdex.size()>=2){
19         int s=maxdex[0];
20         int e=maxdex.back();
21         int w=0;
22         for(int i=s;i<=e;i++)
23             w+=maxA[i];
24         return w+water(A,n,start,s)+water(A,n,e,end);
25     }
26     else{
27         int t=maxdex[0];
28         int maxleft=A[start];
29         int leftindex=start;
30         for(int i=start;i<t;i++){
31             if(A[i]>maxleft){
32                 maxleft=A[i];
33                 leftindex=i;
34             }
35         }
36         int maxright=A[end];
37         int rightindex=end;
38         for(int i=end;i>t;i){
39             if(A[i]>maxright){
40                 maxright=A[i];
41                 rightindex=i;
42             }
43         }
44         A[t]=maxleft;
45         int lwater=water(A,n,leftindex,t)+
46                    water(A,n,start,leftindex);
47         A[t]=maxright;
48         int rwater=water(A,n,t,rightindex)+
49                    water(A,n,rightindex,end);
50         return lwater+rwater;
51     }
52 }
53 
54 int trap(int A[], int n) {
55         return water(A,n,0,n1);
56 }
Advertisements
This entry was posted in Array and linked list, Divide and Conquer. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s