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