Create a tree to save routes (x,y)

[bufoss]

Hi all,
I am using the following structure in order to save the map, the start postion and the number of
columns and rows of a maze

struct mazeStruct {
    char **map;
    int x, y;
    int rows, columns;
};

The maze consists of '#' and ' ' (spaces). For example,

####################
#                  #
# ###### ###########
# ###              #
# ######### ########
# ### #   # ########
####################

Given a start position I want save in a tree and print all the valid routes (not diagonial moves). For example,
if I start in position (2,1)

####################
#                  #
#H###### ###########
# ###              #
# ######### ########
# ### #   # ########
####################

I think that I need a new structure as follow :

struct node
{
   char value;
   int x, y;
   struct node* left;
   struct node* right;
   struct node* up;
   struct node* down;
};

struct node* newnode(int x, int y, char value)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->x = x;
  node->y = y;
  node->value = value;
  node->left  = NULL;
  node->right = NULL;
  node->up = NULL;
  node->down = NULL;
  
  return(node);
}


void printPaths(struct node* node) 
{
  int path[1000];
  printPathsRecur(node, path, 0);
}
 

void printPathsRecur(struct node* node, int path[], int pathLen) 
{
  if (node==NULL) 
    return;
 
  /* append this node to the path array */
  path[pathLen] = node->value;
  pathLen++;
 
  /* it's a leaf, so print the path that led to here  */
  if (node->left==NULL && node->right==NULL && node->up==NULL && node->down==NULL) 
  {
    printArray(path, pathLen);
  }
  else
  {
    /* otherwise try subtrees */
    printPathsRecur(node->left, path, pathLen);
    printPathsRecur(node->right, path, pathLen);
    printPathsRecur(node->up, path, pathLen);
    printPathsRecur(node->down, path, pathLen);
  }
}


int main()
{
	struct mazeStruct maze;
    //read a maze and assign to the struct

	struct node *root = newnode(maze.x, maze.y, maze.map[maze.x][maze.y]);
	
}

but I don;t know how to continue
Could you please help me ?

[tpb]

Repost the maze between [output] [/output] tags to retain spacing.

I don't see why a tree is needed. You can do the same thing just walking around the maze matrix.
And doesn't a maze need an ending point as well as a starting point?

[bufoss]

Output formatted.Thanks

It is for educational reasons. I dnt care about the end point.
I want only to print all routes from starting point (saved in a tree)

[dhayden]

It is for educational reasons. ... I want only to print all routes from starting point (saved in a tree)

Why must you save it in a tree? If you're having trouble figuring out how to do it, then perhaps a tree isn't the best data structure. To enhance your education, you should concentrate on the inputs and outputs first. Don't lock yourself into a particular data structure. Trust me, I've seen program designs go completely off the rails by making early assumptions like this.

I'd do it as follows (pseudocode):

findPaths(mazeStruct &maze, path &curPath)
{
    // curPath is the path so far. Data structure TBD.
    // store maze.x and maze.y
    for each square neighboring the current position {
        if (the square is a wall) continue;
        if (the square is on the current path) continue;
        // if you get here then the square is unoccupied
        set maze.x and maze.y to the square
        set maze.map[x][y] to indicate that it's on the path.
        add x,y to curPath
        findPaths(maze, curPath)
        // now undo stuff to get it back to current state
        // remove x,y from curPath
        set maze.map[x][y] to indicate that it isn't on the path
    }
    If (you didn't find anywhere to move in the for loop) {
        // You found a dead end
        print the curPath. You might do this by just printing the maze since you marked
        the path above.
    }
    restore maze.x and maze.y to their original values
}