Runtime Error for unknown reason, I gave up


  • 0
    Y
    class Solution {
    public:
        struct CompareClass {
            bool operator() (pair<int,pair<int,int>> n1, pair<int,pair<int,int>> n2) {
                return n1.first > n2.first;
            }
        };
        int trapRainWater(vector<vector<int>>& heightMap) {
            int m = heightMap.size();
            if (m == 0) return 0;
            int n = heightMap[0].size();
            
            //Initial flag matrix which height is already pushed in Heap
            vector<bool> tmp1(n,false);//false means searched
            vector<bool> tmp2(n,true); 
            tmp2[0] = false; 
            tmp2[n-1] = false;
            vector<vector<bool>> flag;
            flag.push_back(tmp1);
            for(int i = 0; i < m-2; i++)
                flag.push_back(tmp2);
            flag.push_back(tmp1);    
            
            //Initial minHeap instore surrounded elements; 
            priority_queue< pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, CompareClass> minHeap;// <height,<i,j>>
            for(int i = 0; i < n; i++) { //first & last row
                minHeap.push(make_pair(heightMap[0][i],make_pair(0,i)));
                minHeap.push(make_pair(heightMap[m-1][i],make_pair(m-1,i)));
            }
            for(int i = 1; i < m-1; i++) {//first & last column
                minHeap.push(make_pair(heightMap[i][0],make_pair(i,0)));
                minHeap.push(make_pair(heightMap[i][n-1],make_pair(i,n-1)));
            }
            
            //Check
            int res = 0;
            while(!minHeap.empty()) {
                cout<<"StartCheck: Heap Size = "<< minHeap.size()<<endl;
                pair<int,pair<int,int>> low = minHeap.top();
                minHeap.pop();
                int p = low.first;
                int x = low.second.first;
                int y = low.second.second;
                cout<< "p = " << p <<" ["<<x<<", "<<y<< "]"<< endl;
                if(x-1 >= 0 && flag[x-1][y]) {
                    cout<<"K1"<< endl;
                    flag[x-1][y] = false;
                    if(heightMap[x-1][y] < p) res += p-heightMap[x-1][y];
                    minHeap.push(make_pair(heightMap[x-1][y],make_pair(x-1,y)));
                    cout<< "Push ["<< x-1<<", "<<y<<"]"<< endl;
                }
                if(x+1 <= n-1 && flag[x+1][y]) {
                    cout<<"K2"<< endl;
                    flag[x+1][y] = false;
                    if(heightMap[x+1][y] < p) res += p-heightMap[x+1][y];
                    minHeap.push(make_pair(heightMap[x+1][y],make_pair(x+1,y)));
                    cout<< "Push ["<< x+1<<", "<<y<<"]"<< endl;
                }
                if(y-1 >= 0 && flag[x][y-1]) {
                    cout<<"K3"<< endl;
                    flag[x][y-1] = false;
                    if(heightMap[x][y-1] < p) res += p-heightMap[x][y-1];
                    minHeap.push(make_pair(heightMap[x][y-1],make_pair(x,y-1)));
                    cout<< "Push ["<< x<<", "<<y-1<<"]"<< endl;
                }
                if(y+1 <= m-1 && flag[x][y+1]) {
                    cout<<"K4"<< endl;
                    flag[x][y+1] = false;
                    if(heightMap[x][y+1] < p) res += p-heightMap[x][y+1];
                    minHeap.push(make_pair(heightMap[x][y+1],make_pair(x,y+1)));
                    cout<< "Push ["<< x<<", "<<y+1<<"]"<< endl;
                }
                cout<<"EndCheck res = "<< res <<endl;
            }
            return res;
        }
    };```
    
    **Test Case**
    ```[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]```
    
    **StdOut:**
    ```StartCheck: Heap Size = 14
    p = 1 [0, 0]
    EndCheck res = 0
    StartCheck: Heap Size = 13
    p = 1 [0, 3]
    K2
    Push [1, 3]
    EndCheck res = 0
    StartCheck: Heap Size = 13
    p = 1 [2, 5]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.