How do I print the movement path using a stack(in C99)?

I implemented a maze using a stack in this data structure class. However, the challenge is to use the stack in this code to output the maze's path, including the process of returning to the way it came when it reached a coordinate that could no longer be moved. I tried to solve it with ChatGPT, but I was not satisfied with the results, so I'm asking for help like this.

Here is my code.

#define MAZE_SIZE 10
#define MAX_STACK_SIZE 100
#include <stdio.h>
int back_count ;
typedef struct {
short r ;
short c ;
} element;
typedef struct {
int top ;
element data[MAX_STACK_SIZE];
} StackType ;
void init_stack(StackType *s) {
s->top = -1 ;
}
int is_empty(StackType *s) {
return (s->top == -1);
}
int is_full(StackType *s) {
return (s->top == MAX_STACK_SIZE - 1) ;
}
void push(StackType *s, element item) {
if (is_full(s)) {
fprintf(stderr, "Stack Full") ;
return;
}
else {
s->data[++(s->top)] = item ;
}
}
element pop(StackType *s) {
if (is_empty(s)) {
fprintf(stderr, "Stack Empty") ;
element err = {-1, -1};
return err;
}
else {
return (s->data[(s->top)--]) ;
}
}
element here = {1, 0}, entry = {1, 0};
char maze[MAZE_SIZE][MAZE_SIZE] = {
{'1','1','1','1','1','1','1','1','1','1'},
{'e','1','0','1','0','0','0','1','0','1'},
{'0','0','0','1','0','0','0','1','0','1'},
{'0','1','0','0','0','1','1','0','0','1'},
{'1','0','0','0','1','0','0','0','0','1'},
{'1','0','0','0','1','0','0','0','0','1'},
{'1','0','0','0','0','0','1','0','1','1'},
{'1','0','1','1','1','0','1','1','0','1'},
{'1','1','0','0','0','0','0','0','0','x'},
{'1','1','1','1','1','1','1','1','1','1'}
} ;
void push_loc(StackType *s, int r, int c) {
if(r<0 || c<0) {
return ;
}
if(maze[r][c] != '1' && maze[r][c] != '.') {
element tmp ;
tmp.r = r ;
tmp.c = c ;
push(s, tmp) ;
}
}
void maze_print(char maze[MAZE_SIZE][MAZE_SIZE]) {
printf("\n") ;
for(int r=0; r<MAZE_SIZE; r++) {
for(int c=0; c<MAZE_SIZE; c++) {
printf("%c", maze[r][c]) ; 
}
printf("\n") ;
}
}
int backcount(int r, int c) {
if ((maze[r + 1][c] == '1' || maze[r + 1][c] == '.') && (maze[r - 1][c] == '1' || maze[r - 1][c] == '.') && (maze[r][c + 1] == '1' || maze[r][c + 1] == '.') && (maze[r][c - 1] == '1' || maze[r][c - 1] == '.'))
{
back_count++;
}
return back_count;
}
int main(void) {
int r, c ; 
StackType s ;
init_stack(&s) ;
here = entry ;
while(maze[here.r][here.c] != 'x') {
r = here.r ;
c = here.c ;
maze[r][c] = '.' ;
maze_print(maze) ;
push_loc(&s, r-1,c) ;
push_loc(&s, r+1,c) ;
push_loc(&s, r,c-1) ;
push_loc(&s, r,c+1) ;
backcount(r, c) ;
if(is_empty(&s)) {
printf("Fail\n") ;
return 0 ;
}
else {
here = pop(&s) ;
}
} 
printf("Success\n") ;
printf("Back count : %d\n", backcount(r, c)) ;
return 0 ;
}

I made another stack to push all the movement paths and printed it out, and the output is from (1,4) to (4,3) of this maze.

This is the path that will produce the output I want.

Path to exit :
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(3, 3)
(3, 4)
(2, 4)
(2, 5)
(2, 6)
(1, 6)
(1, 5)
(1, 4)
(1, 5)
(1, 6)
(2, 6)
(2, 5)
(2, 4)
(3, 4)
(3, 3)
(4, 3)
(4, 2)
(4, 1)
(5, 1)
(5, 2)
(5, 3)
(6, 3)
(6, 4)
(6, 5)
(7, 5)
(8, 5)
(8, 6)
(8, 7)
(8, 8)

To clarify, your goal is to solve the maze, but also to provide the path that the algorithm found, correct?

Right now, when you are standing on a cell, you are storing all bordering cells in the stack. This is fine for saving a list of cells that you have not yet explored, but it isn't good for storing the path that you have taken up to now.

For instance, say you have this maze:

// e = entrance, x = exit, 0 = path, 1 = wall
col 0 1 2
row
0   1 0 1
1   0 e x
2   1 0 1

The exit is right next to the entrance. With your approach, on the first iteration of the loop you would put all tiles next to the e into the stack, like this:

Stack:
0: (0, 1)  // above e
1: (2, 1)  // below e
2: (1, 0)  // left of e
3: (1, 2)  // right of e

Then you would pop the top from the stack, which is the cell right of the entrance, you see that it is the exit, and then your program is done.

But the state of the stack still looks like this:

Stack:
0: (0, 1)  // above e
1: (2, 1)  // below e
2: (1, 0)  // left of e

Which if you were to show it visually, is this:

. o .
o . .
. o .

The stack does not at all reflect the path that got you to the end. Instead, it reflects all of the tiles that you didn't visit in order to find the end.

Instead, try to invert the way that you use the stack. Instead of storing all of the cells that you didn't visit, try storing all of the cells that you did visit. That way you can use the stack to store the path that you took to get to your current location.

• Main Loop:
  • Check all 4 neighboring cells, and for every single one, do this:
    • if it is the exit, push the current location and that of the neighbor onto the stack, and then exit the Main Loop.
    • if it is an empty space, push the current location onto the stack and begin the next iteration of the Main Loop
    • if it is a wall or already visited, do nothing and continue checking the other neighbors of the current cell
  • You've checked all neighboring cells and could not find one to go to. This means we have to take a step back because we can't get to the exit from here.
    • mark this cell as "visited" (you were using the '.' character for this)
    • pop a cell from the stack, this is your new location (if you can't because the stack was empty, then the maze is unsolvable)
• The stack now holds the path you took to get to the exit.

This is roughly what you main function should look like, I haven't tested it for syntax errors, but the comments should make it clear what is happening at each step:

element neighbors[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

while (true) {

  bool exit_found = false, took_step = false;

  // Check all 4 neighbors
  for (int i = 0; i < 4; i++) {
    int r = here.r + neighbors[i].r; // neighboring row
    int c = here.c + neighbors[i].c; // neighboring column
    char neighbor = maze[r][c];

    if (neighbor == 'e') {
      // The exit! The maze is solved.

      // The stack holds the path that is behind us,
      // complete the path by adding the current location and the exit.
      push_loc(&s, here.r, here.c);
      push_loc(&s, r, c);

      exit_found = true;
      break; // Stop checking the neighbors
    }

    if (neighbor == '0') {
      // A new path we can go! Take a step forward.

      // The stack holds the path behind us,
      // add our current location to it and then move to the new location.
      push_loc(&s, here.r, here.c);
      here.r = r;
      here.c = c;

      took_step = true;
      break; // Stop checking the neighbors.
    }

    // If the neighbor is anything other than exit or empty, (visited, or wall)
    // then we do nothing and keep checking the other neighbors.
  }

  // Depending on what we found, what should we do?
  if (exit_found) break; // We're done!
  if (took_step) continue; // We're on a new location now, repeat the process!

  // We've checked all neighboring and we didn't take a step or found the exit.
  // That means we have to take a step back because we can't get to the exit from here.

  // Mark this cell as visited.
  maze[here.r][here.c] = '.';

  // Make sure we can still pop from the stack.
  if (is_empty(&s)) {
    printf("unsolvable");
    exit(-1);
  }

  // Take a step back.

  // stack = [loc1, loc2, loc3, loc4], here = loc5
  here = pop(&s);
  // stack = [loc1, loc2, loc3],       here = loc4
}


printf("The path to the exit is:\n");

for (int i = 0; i <= s.top; i++) {
  printf("(%d, %d)\n", s.data[i].r, s.data[i].c);
}

I just realized that there are some other issues with your (and my) code, being that when you're checking the neighbors of a tile, you're not checking if those tiles are within the maze's boundaries (for example, indexing -1 on an array, when we're looking to the left of a cell that is already the leftmost cell - the entry point in your example has that problem). That shouldn't be too hard to fix though, you just have to remember to do it because C will not give you any warnings when it happens, it's just that the program may segfault or your results become gibberish.