Как найти весь путь в лабиринте?

Question

Я дал следующий лабиринт

          { 1,1,1,1,1,1,1     0
            1,0,0,0,0,1,1     1
            1,1,1,0,1,1,1     2
            1,1,0,0,0,0,1     3
            1,1,0,1,1,0,1     4
            1,1,0,0,0,0,1     5
            1,1,1,1,1,1,1 }   6

            0 1 2 3 4 5 6

1 означает, что есть стена, 0 означает, что есть открытый путь

Мне нужно начать с (1,1) и закончить sh точка (5, 5), и мне нужно найти весь путь. Я могу go восток, запад, север, юг, северо-восток, юго-восток, юго-запад, северо-запад.

Мне нужно использовать DFS и стек (так как это назначение). На данный момент я написал код, который дает мне только один возможный путь лабиринта. Как изменить его, чтобы найти все пути?

Вот мой код:

#include <stdio.h>
#include <stdlib.h>

#define HEIGHT 7
#define WIDTH 7

#define N 0
#define NE 1
#define E 2
#define SE 3
#define S 4
#define SW 5
#define W 6
#define NW 7

typedef struct _Infor{
    int x;
    int y;
    int direction;
}Infor;

typedef struct _Node{
    Infor *infor;
    struct _Node *next;
}Node;

typedef struct _Stack {
    Node *top;
}Stack;

Infor *create_infor(int x, int y, int direction);
void delete_infor(Infor *infor);



Stack *create_stack(void);

Infor *pop_stack(Stack *stack);
void init_stack(Stack *stack);
int empty_stack(Stack *stack);

void init_stack(Stack *stack);


Infor *create_infor(int x, int y, int direction){
    Infor *tmp_infor;

    tmp_infor = (Infor*)malloc(sizeof(Infor));
    tmp_infor->x = x;
    tmp_infor->y = y;
    tmp_infor->direction = direction;

    return tmp_infor;
}
void delete_infor(Infor *infor){
    free(infor);
}

Stack *create_stack(void){
    Stack *tmp_stack;

    tmp_stack = (Stack*)malloc(sizeof(Stack));
    tmp_stack->top = 0;

    return tmp_stack;
}

void delete_stack(Stack *stack){
    free(stack);
}


void init_stack(Stack *stack){
    Infor *infor;

    while(!empty_stack(stack)){

        infor = pop_stack(stack);
        delete_infor(infor);
    }

}

int empty_stack(Stack *stack){

    if(stack->top==0) return 1;
    else return 0;
}


int push_stack(Stack *stack, Infor *infor){
    Node *tmp_node;

    tmp_node = (Node*)malloc(sizeof(Node));
    tmp_node-> infor = infor;
    tmp_node-> next = stack->top;

    stack->top = tmp_node;
}

Infor *pop_stack(Stack *stack)
{
    Infor *tmp_infor;
    Node *tmp_node;

    tmp_infor = stack->top->infor;
    tmp_node = stack->top;

    stack->top = stack->top->next;
    free(tmp_node);
    return tmp_infor;
}

void print_stack(Stack *stack){
    Node *tmp_node;

    tmp_node = stack->top;
    while (tmp_node!= 0){
        printf("<%d, %d, %d> \n",
               tmp_node->infor->x,
               tmp_node->infor->y,
               tmp_node->infor->direction);
        tmp_node = tmp_node->next;
    }
}

int move(int maze[HEIGHT][WIDTH], int mark[HEIGHT][WIDTH], Stack *stack){
    Infor *infor, *tmp_infor;
    int count = 0;

    infor = stack->top->infor;
    if(infor ->x== HEIGHT - 2 && infor->y == WIDTH - 2){
        print_stack(stack);
        count++;
        return;
    }


    tmp_infor = create_infor(infor->x, infor->y, infor->direction);
    if(infor->direction == NW || infor->direction == N || infor->direction == NE)
        tmp_infor->x -= 1;


    if(infor->direction == SE || infor->direction == S || infor->direction ==SW)
        tmp_infor->x +=1;

    if(infor->direction == NE || infor->direction == E || infor->direction == SE )
        tmp_infor->y+=1;

    if (infor->direction == SW || infor->direction == W || infor->direction == NW)
        tmp_infor->y-=1;
    tmp_infor->direction = N;

    if(mark[tmp_infor->x][tmp_infor->y] == 0 && maze[tmp_infor->x][tmp_infor->y] == 0){
        mark[tmp_infor->x][tmp_infor->y] = 1;
        push_stack(stack, tmp_infor);
        move(maze, mark, stack);
    }
    else {
        delete_infor(tmp_infor);
        tmp_infor = pop_stack(stack);
        if(tmp_infor->direction == NW){
            delete_infor(tmp_infor);
            move(maze, mark, stack);
        }
        else{
            tmp_infor->direction+=1;
            push_stack(stack, tmp_infor);
            move(maze, mark, stack);
        }
    }

}



int main(){

    printf("IM ok0");
    int maze[HEIGHT][WIDTH] = {
            {1,1,1,1,1,1,1},
            {1,0,0,0,0,1,1},
            {1,1,1,0,1,1,1},
            {1,1,0,0,0,0,1},
            {1,1,0,1,1,1,1},
            {1,1,0,0,0,0,1},
            {1,1,1,1,1,1,1}
    };

    int mark[HEIGHT][WIDTH] ={0};

    Stack *stack;
    Infor *infor;
    stack = create_stack();
    infor = create_infor(1,1,N);

    mark[1][1] = 1;

    int fcount;

    push_stack(stack, infor);
    fcount = move(maze, mark, stack);

    int i ,j ;
    for(i = 0; i< HEIGHT; i++)
    {
        for(j =0; j<WIDTH; j++)
        {
            printf("%d ", mark[i][j]);
        }
        printf("\n");
    }
    printf("%d ",fcount);

    return 0;
}