如何在C99中利用栈打印迷宫的完整移动路径（含回溯）

问题描述 #

用栈实现迷宫求解，要求输出完整移动路径，包括走到死路时的回溯过程。现有代码无法实现该需求，尝试用额外栈存储路径但仅输出部分段，期望得到如示例所示的完整路径。

当前实现代码 #

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

期望输出路径 #

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)

修改方案 #

要实现完整路径（包括回溯）的输出，需要维护一个路径栈，记录当前走过的所有节点。当走到死路需要回溯时，从路径栈中弹出节点并记录回溯步骤。

关键修改点： #

1. 添加路径栈path_stack，用于存储当前有效路径。
2. 每进入一个新节点时，将其压入路径栈并打印该节点。
3. 当发现当前节点是死路（弹出的下一个节点不在当前节点的邻域），则从路径栈中弹出节点，打印回溯步骤。

修改后的完整代码 #

#define MAZE_SIZE 10
#define MAX_STACK_SIZE 100

#include <stdio.h>
#include <stdlib.h> // 用于abs函数

int back_count = 0;

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

// 判断两个坐标是否相邻
int is_adjacent(element a, element b) {
    return ((a.r == b.r && abs(a.c - b.c) == 1) || (a.c == b.c && abs(a.r - b.r) == 1));
}

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 || r >= MAZE_SIZE || c >= MAZE_SIZE) {
        return;
    }
    if (maze[r][c] != '1' && maze[r][c] != '.') {
        element tmp;
        tmp.r = r;
        tmp.c = c;
        push(s, tmp);
    }
}

int main(void) {
    int r, c;
    StackType s, path_stack;

    init_stack(&s);
    init_stack(&path_stack);
    here = entry;

    printf("Path to exit :\n");
    // 将起点压入路径栈并打印
    push(&path_stack, here);
    printf("(%d, %d)\n", here.r, here.c);

    while (maze[here.r][here.c] != 'x') {
        r = here.r;
        c = here.c;
        maze[r][c] = '.';

        push_loc(&s, r-1, c);
        push_loc(&s, r+1, c);
        push_loc(&s, r, c-1);
        push_loc(&s, r, c+1);

        if (is_empty(&s)) {
            printf("Fail\n");
            return 0;
        } else {
            element next = pop(&s);
            // 如果下一个节点和当前节点不相邻，说明需要回溯
            while (!is_adjacent(here, next)) {
                // 弹出路径栈顶节点，打印回溯步骤
                element back_node = pop(&path_stack);
                printf("(%d, %d)\n", back_node.r, back_node.c);
                back_count++;
                if (is_empty(&path_stack)) {
                    printf("Fail\n");
                    return 0;
                }
                here = path_stack.data[path_stack.top];
            }
            here = next;
            push(&path_stack, here);
            printf("(%d, %d)\n", here.r, here.c);
        }
    }

    printf("Success\n");
    printf("Back count : %d\n", back_count);

    return 0;
}

修改说明： #

• 新增is_adjacent函数判断两个节点是否相邻，用于检测是否需要回溯。
• 新增path_stack记录当前有效路径，每进入新节点就压入栈并打印。
• 当弹出的下一个节点与当前节点不相邻时，说明当前路径走到死路，从path_stack弹出节点并打印回溯步骤，直到找到与下一个节点相邻的路径节点。
• 修正了push_loc的边界判断，增加了对r >= MAZE_SIZE和c >= MAZE_SIZE的检查，避免数组越界。
• 初始化back_count为0，避免未初始化的垃圾值影响统计结果。

内容的提问来源于stack exchange，提问作者MINOKIM