Hey guys, i'm working on a recursive problem that invlolves getting from a place "s" (start) to a part "e" (end) in as few moves as possible. There are road blocks "x" and the grid is a size up to 15x15. My problem is that when I try to write a recursive function to move throughout the maze, I keep seg faulting. A picture of what the grid looks like is attached.

As far as I know, the reason is because I am moving outside the bounds of the matrix and thus the program seg faults. I'm confused as to why though because I feel like I have the limitations in place to stop it from doing that. The majority of the code is reading in from the file, but you'll see ////RECURSIVE /// towards the lower third of the code, this is where I go wrong.

Thanks and any guidance or help is appreciated!

/*
 *  grid.cpp
 *
 *  Created by Alec on 10/31/10.
 *
 */

using namespace std;

#include <iostream>
#include <string>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <cstdlib>

int convertStreet(string street, int size);
bool checkStreet(string street);
int findPath(string matrix[16][16],int sStreet, int sAvenue, int eStreet, int eAvenue,int size, string counter[],int counter);



int main(){

	int size; // holds size of grid
	int ud; // up down
	int lr; // left right
	int aHolder; // avenue holder
	int temp1; // various temps to hold values while inserting into grid
	int temp2; // temp
	int temp3; // temp
	int startAve;
	int startStreet;
	int endAve;
	int endStreet;
	string word; // used in the stringstream for file reading
	string alphabet[15] = {"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O"};
	string numbers[25]  = {"1","2","3","4","5","6","7","8","9","10","11","12","13","14","15","16","17","18","19","20","21","22","23","24","25"};
	string line;
	string info;
	ifstream gridIn;
	ofstream paths;
	gridIn.open("grid.in");
	if(!gridIn)
	{
		cout << "There was a problem opening/reading the grid file. Please check for file";
		return(1);
	}
			
			
	//beginning to read from file
	gridIn >> size;
	int sizeMat = size+1;
	//cout << sizeMat;
	string matrix[16][16];// plus one because we want row column to hold street avenue
	//            ROW     COLUMN
	
	int k;
	int j;
	
	for (int j=0; j <= size; j++) {
		
		for (k = 0; k <= size; k++) {
			
			if(k == 0 && j != size){ // stop one short to avoid array out of bounds but put in correct letters
			
				matrix[j][k] = alphabet[(size - j)-1]; // a, b, c, d for the streets
							 
			}
		
			else {
				matrix[j][k] = "";

			}

		}
	}
	
	int row = size;
	
	for (int column = 1; column <= size; column++) { // putting numbers into the matrix correctly
		matrix[row][column] = numbers[column-1];
	}
	

	while (getline(gridIn,line))
    {
		int i = 0;
		stringstream stream(line);
		string type = "";
		while( getline(stream, word, ' ') )
		{
			
			//manipulation of the code here
			//checking to see if it is start end or road block (first letter)
			if( i==0 && word=="s")
			{
				type = "start";
			}
			else if( i==0 && word =="e")
			{
				type = "end";
			}
			else if(i == 0 && checkStreet(word)){
				type = "street";
				temp1 = convertStreet(word, size); // holds the street matrix value
				
			}
			else if(i == 0 && !checkStreet(word)){
				type = "avenue";
				temp2 = convertStreet(word, size); // holds the avenue matrix value
				
			}
			
			// after already reading from first word, now check the remaining two
			if(type == "start")
			{
				if(i==1)
				{
					string temp1 = word;
					lr = convertStreet(temp1, size);
				}
				else if(i==2) {
					string temp = word;
					
					ud = convertStreet(temp, size);					
					matrix[ud][lr] = "S";
					startStreet = ud;
					startAve = lr;
					
				}

			}
			
			else if(type =="end")
			{
				if(i==1)
				{
					string temp1 = word;
					lr = convertStreet(temp1, size);
				}
				else if(i==2) {
					string temp = word;
					
					ud = convertStreet(temp, size);					
					matrix[ud][lr] = "E"; // variables backwards here because of movement based on variables
					endStreet = ud;
					endAve = lr;
					
				}

				
			}
			
			else if(type == "street")
			{
				if(i==1)
				{
					string temp1 = word;
					//cout << word;
					lr = convertStreet(temp1, size);
				}
				else if(i==2) {
					string temp = word;
					ud = convertStreet(temp, size);	
					
					for (lr; lr <= ud; lr++) {
						matrix[temp1][lr] = "x";

					}
					
				}
			} 
				
			else if(type == "avenue")
			{
				if(i==1)
				{
					string tempA = word;
					aHolder = convertStreet(tempA, size); // aHolder. 4 then 2 in test case
				}
				else if(i==2) {
					string temp = word;
					temp3 = convertStreet(temp, size); // temp 1. 1	test case
					
					for (temp3; temp3 <= aHolder; temp3++) {
						matrix[temp3][temp2] = "x";
						
					}
					
				}
			} 
			
			i++;
        } // end of getword
		
				
    } // end of getline
	matrix[size][0] = "-";	
	
	// print out the matrix
	int i = 0;
	j = 0;
	cout << "The given matrix is:\n" ;
	for( i=0; i <= size; i++)
	{
		cout<<"\n";
		
		for( j=0; j<= size; j++)
		{
			cout<< setw(2) <<matrix[i][j];
        }
    }   
	
	
	// end print
	// call recursive function!
	int c = 0;
	
	//findPath(matrix, startStreet, startAve, endStreet, endAve, size, numbers, c);
	
			
	}
//// RECURSIVE FUNCTION ////////////////
int findPath(string matrix[16][16],int sStreet, int sAvenue, int eStreet, int eAvenue,int size, string counter[], int n){
	
	// going down
	
	if ((sStreet+1) != (size) && matrix[sStreet+1][sAvenue] == "") {
		matrix[sStreet+1][sAvenue] = counter[n];
		findPath(matrix,sStreet+1,sAvenue,eStreet,eAvenue, size, counter, n+1);
			   
	}
	
	 //going up
	if (sStreet != 0 && sStreet != (size) && sStreet != (size-1)) {
		
	
	if (sStreet != 0 && sAvenue != (size-1) && matrix[sStreet-1][sAvenue] == "") {
		matrix[sStreet-1][sAvenue] = counter[n];
		findPath(matrix,sStreet-1,sAvenue,eStreet,eAvenue,size, counter, n+1);
	}
		}
	
	//going left
	if (matrix[sStreet][sAvenue-1] == "") {
		matrix[sStreet][sAvenue-1] = counter[n];
		cout << "when going left - start street = " << sStreet << endl;
		findPath(matrix,sStreet,sAvenue-1,eStreet,eAvenue,size, counter, n+1);
	}
	
	//going right
	if ( matrix[sStreet][sAvenue+1] == "") {
		matrix[sStreet][sAvenue+1] = counter[n];
		findPath(matrix,sStreet,sAvenue+1,eStreet,eAvenue,size,counter,n+1);
	}
						  
	
	// matrix[sStreet][sAvenue]
	
	/////////// PRINT ////////
	int i = 0;
	int j = 0;
	cout << "\nThe given matrix is:\n" ;
	for( i=0; i <= size; i++)
	{
		cout<<"\n";
		
		for( j=0; j<= size; j++)
		{
			cout<< setw(3) <<matrix[i][j];
        }
    } 
 	//////// END PRINT /////////
		
}
////////////////////////////////////

bool checkStreet(string street){
	
	string checks[15] = {"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O"};
	
	for (int i = 0; i < 15; i++) {
		
		if(street == checks[i]) {
			return 1;
		}
		   
	}
	
	return 0;
	
}


int convertStreet(string street, int size){
	int corrNum;
	
	if (street == "A") {
		corrNum = size - 1;
	}
	else if(street == "B"){
		corrNum = size - 2;
	}
	else if(street == "C"){
		corrNum = size -3;
	}
	else if(street == "D"){
		corrNum = size -4;
	}
	else if(street == "E"){
		corrNum = size -5;
	}
	else if(street == "F"){
		corrNum = size -6;
	}
	else if(street == "G"){
		corrNum = size -7;
	}
	else if(street == "H"){
		corrNum = size - 8;
	}
	else if(street == "I"){
		corrNum = size - 9;
	}
	else if(street == "J"){
		corrNum = size -10;
	}
	else if(street == "K"){
		corrNum = size -11;
	}
	else if(street == "L"){
		corrNum = size -12;
	}
	else if(street == "M"){
		corrNum = size -13;
	}
	else if(street == "N"){
		corrNum = size -14;
	}
	else if(street == "O"){
		corrNum = size -15;
	}
	
	string nums[15]={"1","2","3","4","5","6","7","8","9","10","11","12","13","14","15"};
	for (int j = 0; j<15; j++) {
		
	 if(street == nums[j]){
		corrNum = (j +1);
		}
	  }
	
	
	return corrNum;
}

Edited 6 Years Ago by Alec0905: n/a

Attachments Screen_shot_2010-11-12_at_7.28_.34_PM_.png 11.58 KB

Hi,

I assumes matrix has created properly from the input,
Two things i notice in the recursion:

1) You are not checking the range of the matrix, -1 can lead you to matrix[-1][0] which is an invalid memory, thats why you are getting segmentation fault.

2) You are not keeping visited and unvisited tracks.

Thank you for the response. As for your two statements, I feel like i'm doing them both.

1) in the if statement for the going up I have if(sStreet !=0 ...), that alone should stop the function from running if it is trying to take a 0 street and subtract it by 1, thus giving me the out of bounds seg fault.

2) because i'm checking to see in the if statement if the matrix spot == "", or is empty, if it has been visited it won't be empty and thus the function won't go there.

Am I implementing these wrong or is something else going on?

Thanks again.

Edited 6 Years Ago by Alec0905: spelling

what about this one? matrix[0][-1] is also invlid memory space.

if (matrix[sStreet][sAvenue-1] == "") {
//codes
}

you have to check all the boundary, not only -1 also for +1

And about the visited, unvisited,

You are not making unvisited after the recursion.

//logic of the recurstion

void RecursionMethod(city){

  for(all adjacent cities)
    if(path exists to city and city not visited){
        visited[city] = true;
         RecursionMethod(city);
        visited[city] = false;
  }

}

Hope it helps.

Debug every step slowly and see the values of your paths and decision you are making.

BTW, this problem is better suited for BFS not DFS. but DFS should also give you the result.

The second part helped, i've fixed my seg fault issues, thanks!

This question has already been answered. Start a new discussion instead.