My code below for SPOJ WATER Problem is running fine in ideone and locally but its giving SIBABRT runtime error while submitting solution.
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;
}