-1

My code below for SPOJ WATER Problem is running fine in ideone, glot and locally but its giving SIBABRT runtime error while submitting solution.

My solution, though not optimized roughly follows below algorithm

  1. Sort graph based on least level/height.
  2. Iterate over sorted graph, and reach least node one by one and do 3 & 4.
  3. Fill the node with the value of least surrounding wall
  4. FloodFill: Fill the entire surface(multiple nodes) of new level/height in 3 with least surrounding wall.
  5. Abort floodfill,if going outside area or if any lower surface found.

I generated multiple datasets and cross checked results with other accepted solutions and it appears to produce correct results but i am unable to submit due to this error.

Please help me in understanding what could be the reason behind it. Thanks in advance!

#include <iostream>
#include<queue>
#include<stack>
#include<string>
#include<climits>
#include<algorithm>
#include<sstream>

using namespace std;


void convertStringToVector(vector<int>& v, string& data, char delim =  ' '){
    stringstream ss(data);
    string numstr;
    while(getline(ss, numstr, delim )){
        v.push_back(stoi(numstr));
    }
}

typedef struct Node{
    int value;
    bool visited;
    int pos;
    Node(int val, int pos, bool isvisited = false){
        this->value = val;
        
        this->pos = pos;
        this->visited = isvisited;
    }
}Node;



typedef struct Tank{
    int level;
    Tank(int capacity = 0){
        this->level = capacity;
    }
}Tank;

void fillSpot(int index,int level, vector<Node>& graph, vector<Node>& ograph, Tank& tank, int rmax, int cmax){
    int pos = graph[index].pos;
    vector<int> rr = {1,-1,0,0};
    vector<int> cc = {0,0,1,-1};
    Node& currentNode = ograph[pos];
    int x = int(pos / cmax);
    int y = pos % cmax;
    int min = INT_MAX;
    int currentLevel = currentNode.value;
    for(int i = 0; i< rr.size(); i++){
        int newx = x + rr[i];
        int newy = y + cc[i];
        
        int newpos = (newx * cmax) + newy;
        if(newx <0 || newy < 0 || newx >=rmax || newy>=cmax){
            return;
        }
        
        int neighbour_level = ograph[newpos].value;
        if(neighbour_level < level || neighbour_level == currentLevel){
            return;
        }
        
        if(neighbour_level > level && neighbour_level < min){
            min = neighbour_level;
        }
        
    }
    if(min < INT_MAX && min > currentLevel ){
        
        tank.level = tank.level + (min - currentNode.value);
        currentNode.value = min;  
    }
};

int explore_neighbours(int currNodePos, vector<Node>& graph, vector<Node>& ograph, Tank& tank, int rmax, int cmax, queue<int>& que, int surfaceHeight){
    Node& currNode = ograph[currNodePos];
    int level = currNode.value;
    int pos = currNode.pos;
    vector<int> rr = {1,-1,0,0};
    vector<int> cc = {0,0,1,-1};
   
    int x = int(pos / cmax);
    int y = pos % cmax;
    int min = INT_MAX;
    for(int i = 0; i< rr.size(); i++){
        int newx = x + rr[i];
        int newy = y + cc[i];
        
        int newpos = (newx * cmax) + newy;
        if(newx <0 || newy < 0 || newx >=rmax || newy>=cmax){
            return -1;
        }
        
        Node& neighbourNode = ograph[newpos];
        int neighbour_level = ograph[newpos].value;
  
      
        if(neighbour_level < surfaceHeight){
            return -1;
        }
       
        if(neighbour_level == level && !neighbourNode.visited){
            neighbourNode.visited = true;
            que.push(neighbourNode.pos);
            
        }
        if(neighbour_level > surfaceHeight && neighbour_level < min && !neighbourNode.visited){
            min = neighbour_level;
        }
        
    }
    return min;
    
};

void fillSurface(int index, vector<Node>& graph, vector<Node>& ograph, Tank& tank, int rmax, int cmax){
    int pos = graph[index].pos;
    queue<int> que;
    stack<int> stk;
  
    const int LOWER_HEIGHT_FOUND = -1;
    int minSurfaceLevel = INT_MAX;
    bool abrupt_break = false;
    
    Node& currentNode = ograph[pos];
    que.push(currentNode.pos);
 
    int currentLevel = currentNode.value;
    while(!que.empty()){
        int currNodePos = que.front();
        que.pop();
        Node& currNode = ograph[currNodePos];
        stk.push(currNodePos);
        currNode.visited = true;
        int newMinSurfaceLevel = explore_neighbours(currNodePos, graph, ograph, tank, rmax, cmax, que, currentLevel);
        if(newMinSurfaceLevel == LOWER_HEIGHT_FOUND){
            abrupt_break = true;
            break;
        }
        
        if(newMinSurfaceLevel > currentLevel && newMinSurfaceLevel < minSurfaceLevel){
            minSurfaceLevel = newMinSurfaceLevel;
        }
    }
    if(abrupt_break){
        while(!que.empty()){
            Node & n = ograph[que.front()];
            que.pop();
            n.visited = false;
        }
    }
    while(!stk.empty()){
        int nodePos = stk.top();
        stk.pop();
        Node& n = ograph[nodePos];
        if(abrupt_break){
            n.visited = false;
        }else if(minSurfaceLevel < INT_MAX){
            tank.level = tank.level + (minSurfaceLevel - currentLevel);
            n.value = minSurfaceLevel;
            
        }
        n.visited = false;
    }
}

void buildGraph(){
    string testcases;
    getline(cin, testcases);
    int testcase = 0;
    while(testcase < stoi(testcases)){
        vector<Node> graph, ograph;
        Tank tank = Tank();
        string dims;
        getline(cin, dims);
        vector<int> dimensions;
        convertStringToVector(dimensions, dims);
        
        int rmax = dimensions[0];
        int cmax = dimensions[1];
        
        for (int i =0 ; i < rmax; i++){
            string row;
            getline(cin, row);
            vector<int> rowdata;
            convertStringToVector(rowdata, row, ' ');
            for(int j= 0; j < cmax; j++){
                int pos = i * cmax + j;
                int val = rowdata[j];
                Node gn = Node(val, pos, false);
                Node ogn = Node(val, pos, false);
                graph.push_back(gn);
                ograph.push_back(ogn);
            }
        }
        
        //sort the graph based on value
        sort(graph.begin(), graph.end(), [](Node const& n1, Node const& n2)->bool{
            return n1.value < n2.value;
        });
        

        for(int i = 0; i < graph.size(); i++){
            Node leastfilledNode = graph[i];
            int position = leastfilledNode.pos;
            int level = leastfilledNode.value;
            fillSpot(i, level, graph, ograph, tank,  rmax, cmax);
            fillSurface(i, graph, ograph, tank,  rmax, cmax);
        }

        cout<<tank.level<<endl;
        
        testcase++;
    }
}

int main() {
    buildGraph();
    return 0;
}
user858582
  • 11
  • 2
  • 1
    *I generated multiple datasets* -- Stop generating the datasets yourself and follow the guidelines [here](https://stackoverflow.com/questions/63046559/code-submission-on-spoj-gives-runtime-error-sigabrt/63048464#63048464) – PaulMcKenzie Oct 09 '20 at 19:35
  • So you're asking about problems on a system that you can't even directly access. That doesn't make good questions usually. In any case, do you know what SIGABRT is caused by? What parts of your code could lead to such conditions? – Ulrich Eckhardt Oct 09 '20 at 19:41
  • Why do you believe you need to input integer data as strings? – PaulMcKenzie Oct 09 '20 at 19:43
  • I suggest you read the data as integers. Adding code that reads in a string, and then attempts to parse the string for the integer data just makes it more than likely you have a mistake in the input routines. – PaulMcKenzie Oct 09 '20 at 21:02

1 Answers1

0
        vector<Node> graph, ograph;
        Tank tank = Tank();
        string dims;
        getline(cin, dims);
        vector<int> dimensions;
        convertStringToVector(dimensions, dims);
        
        int rmax = dimensions[0];
        int cmax = dimensions[1];

Without seeing the input, it's hard to know what went wrong, but I see some early opportunities you could guard against.

What if after getline(cin, dims);, the string is empty, or the number is too small? dimensions is initially empty, and at no point do you verify its size. When you use the first 2 elements of dimensions, you'll definitely invite trouble if they're not there.

I would check for things like that, to make sure the sizes line up with your expectations. Throw std::runtime_error if the input isn't right.

One quick way is to use checked vector access:

    int rmax = dimensions.at(0);
    int cmax = dimensions.at(1);

As you may know, vector::at checks its argument against vector::size, whereas vector::operator[] does not.

Looking over the rest of the code, I didn't notice a single check for failure or assertion of a precondition. It implicitly assumes all is going according to plan. SIGABRT is telling you that assumption is incorrect.

James K. Lowden
  • 7,574
  • 1
  • 16
  • 31