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);
}

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 by Alec0905: n/a

Attachments
2
Contributors
4
Replies
5
Views
7 Years
Discussion Span
Last Post by Alec0905

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 by Alec0905: spelling

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

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

You are not making unvisited after the recursion.

``````//logic of the recurstion

void RecursionMethod(city){

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!