Segmentation Fault

[varmak]

I'm currently trying to code a BFS styled program for an assignment of mine. Logically speaking, I think I have it down but it was taking too long to execute so I removed a for loop, and instead used stf::find from #include <algorithm>. Since then my program keeps crashing at runtime and while debugging I get a Segmentation fault.

The user will input a string of 25 characters that are digits(1-4) with the inclusion of one character("G").

Any and all help will be appreciated. I also apologize in advance for posting my entire code, but I couldn't figure out where the error might be from.


Here is my code:

#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<ctime>
#include<algorithm>

using namespace std;

char directions[4] = {'L', 'R', 'U', 'D'};
//string direcPrint[4] = {"Left", "Right", "Up", "Down"} ;
const int pondSize = 5;

struct frontier{
	int currentPad;
	string currentPath;
	vector <int> previousPads;
	
};

struct solution{
	string pathway;
	int nodesLooked;
	int length;
};

int nextPad(int cPad, int dist, int direc)
{
	//cPad is the index of the current lilypad
	//dist is distance jumped(1-4)
	//direc is the direction(L,R,U,D)
	
	int nPad = -1; //-1 by default
	int currentCol;
	
	if (direc == 0)		//Left
	{
		currentCol = cPad % pondSize;
		if (currentCol >= dist)
		{
			nPad = cPad-dist;		
		}	
	}
	else if (direc == 1)	//Right
	{
		currentCol = cPad % pondSize;
		if (currentCol + dist < pondSize)
		{
			nPad = cPad + dist;
		}
	}
	else if (direc == 2)	//Up
	{
		nPad = max(max(-1, cPad), (dist*pondSize));
	}
	else if (direc == 3)	//Down
	{
		nPad = cPad + (dist*pondSize);
		if (nPad >= (pondSize^2))
		{
			nPad = -1;
		}
	}
	else
		nPad = -1;
	
	return nPad;
}

solution shortestPath(string pondPath)
{
	int pad;
	string path;
	vector <int> pads;	//Same as previousPads
	vector <int>::iterator it;
	solution sol;
	queue <frontier> fringe;
	frontier currentItem;
	currentItem = {0,"",vector<int>()};
	
	currentItem.currentPad = 0;
	currentItem.currentPath = "";
	currentItem.previousPads.push_back(0);
	
	
	fringe.push(currentItem);
	
	int nodeLooked = 0;
	int i = 0;
	int counting = 0;
	while (!fringe.empty())
	{
		
		frontier currentFringe;
		currentFringe = fringe.front();
		pad = currentFringe.currentPad;
		path = currentFringe.currentPath;
		pads.push_back(currentFringe.previousPads[i]);
		nodeLooked++;
		i++;
		
		if (pondPath[pad] == 'G')
		{
			break;
		}
		
	
		int dist;
		int futurePad;
		
		for(int jump=0; jump<4; jump++)
		{
			char temp = pondPath[pad];
			dist = (int)temp;
			futurePad = nextPad(pad, dist, jump);
			
			if (futurePad != -1)
			{
				it = find(pads.begin(), pads.end(), futurePad);
					if(it != pads.end())
					{
						
						break;
					}
					else
					{
						//i++;
						string futurePath = path + directions[jump];
						pads.push_back(futurePad);
						currentFringe.currentPad = futurePad;
						currentFringe.currentPath = futurePath;
						currentFringe.previousPads = pads;
						fringe.push(currentFringe);
					}
			} 
			
		}
		path = "No way to the solution!!";
	}
	
	sol.pathway = path;
	sol.nodesLooked = nodeLooked;
	sol.length = fringe.size();
	
	return sol;
}


int main()
{
	solution answer;
	string userInput = "";
	clock_t t1, t2;
	cout<<"Please enter your string: ";
	getline(cin, userInput);
	cout<<"This is the pond that you have entered: "<<endl;
	cout<<userInput<<endl;
	t1 = clock();
	cout<<clock();
	answer = shortestPath(userInput);
	t2 = clock();
	cout<<endl<<t2<<endl;
	cout<<endl;
	cout<<"The solution is: "<<answer.pathway<<endl;
	cout<<"Nodes looked at: "<<answer.nodesLooked<<endl;
	cout<<"Nodes not looked at: "<<answer.length<<endl;
	float diff ((float)t2-(float)t1);
    cout<<"time is: "<<diff<<endl;
    
    system("PAUSE");
    return 0;
	
}

[varmak]

So a user enters a string,
Ex: "232413213111232433331411G"

Which then co-relates to something like this:
2 3 2 4 1
3 2 1 3 1
1 1 2 3 2
4 3 3 3 3
1 4 1 1 G

Essentially, you can jump left(L), right(R), up(U) or down(D) the number of spaces depending on the number at that index.

The end result will be the shortest path to G. So for the given example the solution would be: RDRD

[Thomas1965]

The crash happens at pads.push_back (currentFringe.previousPads[i]); previousPads size is 1 and i is 1 so classical out of range error

[varmak]

I've changed "i" to "0". Because I need to keep looking at the first element. And I've added fringe.pop() in my if else of my for loop.

It gives me an infinite loop now.

[ne555]

show your updated code.
also, comment your `shortestPath()' function


run through a debugger, you may send an interrupt signal (<C-c>) and then perform a backtrace.