C语言迷宫问题

我会带着你远行 2022-03-15 16:56 318阅读 0赞

**主要思路：**  
1. 用一个包含坐标和方向的结点数据类型来存储迷宫中的结点；  
2. 将当前结点压入路径栈，探测该结点各方向是否存在通路；  
3. 若存在通路，则修改该结点方向为通路方向；  
4. 若不存在通路，则将当前结点出栈（实现路径回溯），继续探测上一个通路结点的剩余方向的通路情况，直至找到通路或发现该迷宫无通路，结束进程。  
**关键：**  
要注意迷宫边界点方向探测的条件限定，否则会产生不可预测的结果。

/*-----------------------------------------------
    功能：迷宫问题，寻找一条简单通路（无重复路径）
    输出示例：
    The path from (0, 0) to (5, 5) is:
    (0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2) ->
    (2, 3) -> (3, 3) -> (4, 3) -> (4, 4) -> (4, 5) ->
    (5, 5)
    Author: Zhang Kaizhou
    Date: 2019-3-7 17:34:41
    ------------------------------------------------*/
    #include <stdio.h>
    #include <stdlib.h>
    #define MAXSIZE 1000
    #define N 6
    int maze[N][N] = {
       {0, 0, 1, 1, 1, 1},
                      {1, 0, 1, 1, 1, 1},
                      {1, 0, 0, 0, 1, 1},
                      {1, 1, 1, 0, 1, 1},
                      {1, 1, 1, 0, 0, 0},
                      {1, 1, 1, 1, 1, 0}}; // 用一个全局二维数组构造迷宫，0为通路
    
    typedef struct{ // 定义迷宫中的一个点数据类型
        int pos[2]; // 点的坐标
        int direction; // 当前点到下一个通路的方向，分别用0, 1, 2, 3表示上，右，下，左
    } Node;
    
    typedef struct{ // 定义一个路径栈，用于存放通路结点
        Node data[MAXSIZE];
        int top;
    } NodeStack;
    
    void compute_maze_path(int * start, int * end, NodeStack * correct_path);
    void print_path(NodeStack * correct_path);
    void push_node(NodeStack * pns, Node node);
    void pop_node(NodeStack * pns, Node * node);
    void get_top_node(NodeStack * pns, Node * node);
    
    int main(){
        int start[2] = {0, 0};
        int end[2] = {5, 5};
        NodeStack * correct_path = (NodeStack *)calloc(1, sizeof(NodeStack)); // 用一个路径栈来存放通路结点
        compute_maze_path(start, end, correct_path);
        printf("The path from (%d, %d) to (%d, %d) is:\n", start[0],start[1], end[0], end[1]);
        print_path(correct_path);
    
        free(correct_path);
        return 0;
    }
    
    void compute_maze_path(int * start, int * end, NodeStack * correct_path){
        NodeStack * pns = (NodeStack *)calloc(1, sizeof(NodeStack)); // 定义一个通路栈用于存放通路结点和路径回溯
        pns->top = -1; // 初始化栈顶指针
        Node cur_node;
        int i = 0, done = 0, x, y;
        cur_node.pos[0] = start[0];
        cur_node.pos[1] = start[1];
        cur_node.direction = -1;
        push_node(pns, cur_node);
        maze[start[0]][start[1]] = -1; // 走过的通路结点置为-1，避免路径重复以及路径死循环
        while(pns->top >= 0){
            get_top_node(pns, &cur_node);
            if(cur_node.pos[0] == end[0] && cur_node.pos[1] == end[1]){ // 若为出口通路结点
                while(pns->top >= 0){
                    pop_node(pns, &correct_path->data[i++]);
                }
                correct_path->top = i; // 存放路径长度
                free(pns);
                return;
            }else{ // 若为非出口通路结点
                done = 0;
                while(cur_node.direction < 4 && done == 0){ // 穷举测试各方向通路
                    cur_node.direction++;
                    /*边界检测*/
                    if(cur_node.pos[0] == 0 && cur_node.direction == 0){ // 上边界，方向为上时
                        cur_node.direction = 1;
                    }
                    if(cur_node.pos[1] == 0 && cur_node.direction == 3){ // 左边界，方向为左时
                        cur_node.direction = 4;
                    }
                    if(cur_node.pos[0] == N - 1 && cur_node.direction == 2){ // 下边界，方向为下时
                        if(cur_node.pos[1] == 0){
                            cur_node.direction = 4;
                        }else{
                            cur_node.direction = 3;
                        }
                    }
                    if(cur_node.pos[1] == N - 1 && cur_node.direction == 1){ // 右边界，方向为右时
                        if(cur_node.pos[0] == N - 1){
                            cur_node.direction = 3;
                        }else{
                            cur_node.direction = 2;
                        }
                    }
                    switch(cur_node.direction){
                        case 0: x = cur_node.pos[0] - 1; y = cur_node.pos[1]; break;
                        case 1: x = cur_node.pos[0]; y = cur_node.pos[1] + 1; break;
                        case 2: x = cur_node.pos[0] + 1; y = cur_node.pos[1]; break;
                        case 3: x = cur_node.pos[0]; y = cur_node.pos[1] - 1; break;
                    }
                    done = maze[x][y] == 0 ? 1 : 0;
                }
                if(done == 1){
                    pns->data[pns->top].direction = cur_node.direction;
                    cur_node.pos[0] = x;
                    cur_node.pos[1] = y;
                    cur_node.direction = -1;
                    push_node(pns, cur_node);
                    maze[x][y] = -1;
                }else{ // 路径回溯
                    pop_node(pns, &cur_node);
                    maze[cur_node.pos[0]][cur_node.pos[1]] = 0;
                }
            }
        }
        free(pns);
        return;
    }
    
    void print_path(NodeStack * correct_path){
        int i, count = 0;
        for(i = correct_path->top - 1; i >= 0; i--){
            if(i == 0){
                printf("(%d, %d)\n", correct_path->data[i].pos[0], correct_path->data[i].pos[1]);
            }else{
                printf("(%d, %d) -> ", correct_path->data[i].pos[0], correct_path->data[i].pos[1]);
                count++;
                if(count % 5 == 0){
                    printf("\n");
                }
            }
        }
        return;
    }
    
    void push_node(NodeStack * pns, Node node){
        if(pns->top == MAXSIZE - 1){
            printf("The node stack is full!\n");
        }else{
            pns->top++;
            pns->data[pns->top] = node;
        }
        return;
    }
    
    void pop_node(NodeStack * pns, Node * node){
        if(pns->top < 0){
            printf("The node stack is empty!\n");
        }else{
            * node = pns->data[pns->top];
            pns->top--;
        }
        return;
    }
    
    void get_top_node(NodeStack * pns, Node * node){
        if(pns->top < 0){
            printf("The node stack is empty!\n");
        }else{
            * node = pns->data[pns->top];
        }
        return;
    }