数据结构课设迷宫问题

迷宫问题

【问题描述】以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

【基本要求】编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中：(i，j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为z(1，1，1)，(1，2，2)，(2，2，2)，(3，2，3)，(3，1，2)，··。

【测试数据】迷宫的测试数据如下：左上角(1，1)为入口，右下角(8，9)为出口。

???????????????1 ???2 ???3 ???4 ???5 ???6 ???7 ???8

【实现提示】计算机解迷宫通常用的是“穷举求解“方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。

可以二维数组存储迷宫数据，通常设定入口点的下标为(1，1)，出口点的下标为(n，n)。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。

【选作内容】注：可参考教材50页

(l) 编写递归形式的算法，求得迷宫中所有可能的通路；

(2) 以方阵形式输出迷宫及其通路。

#include <stdio.h>
#include <malloc.h>
#include <pthread.h>
#include <unistd.h>
#define M 10
#define N 10 // 测试案例1，2
// #define M 12
// #define N 12 // 测试案例3
typedef struct
{ // 通路记录
    int current_x;
    int current_y;
    int di;
} Box;
typedef struct sNode
{ // 链栈定义
    Box box;
    struct sNode *next;
} *Linkstack;
void push(Linkstack &top, Box box)
{ // 入栈函数
    Linkstack p;
    p = (Linkstack)malloc(sizeof(struct sNode));
    p->box = box;
    p->next = top;
    top = p;
}
Box pop(Linkstack &top)
{
    Linkstack p = top; // 保存当前栈顶节点
    top = top->next;   // 栈顶指针指向下一个节点
    Box box = p->box;  // 获取出栈元素

    free(p); // 释放出栈节点内存空间

    return box;
}

bool isEmpty(Linkstack &top)
{
    if (top == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}
void print_stack(Linkstack top)
{
    Linkstack p;
    p = top;
    while (p)
    {
        printf("(%d,%d,%d)\n", p->box.current_y, p->box.current_x, p->box.di);
        p = p->next;
    }
}
void print_maze(int maze[M][N])
{
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (maze[i][j] == 1)
            {
                printf("■ ");
            }
            if (maze[i][j] == -1)
            {
                printf("★ ");
            }
            if (maze[i][j] == 0)
            {
                printf("□ ");
            }
            if (maze[i][j] == -2)
            {
                printf("○ ");
            }
        }
        printf("\n");
    }
    printf("--------------------\n");
    sleep(1.5);
}
bool DFS(int maze[M][N], int direction[][2], Linkstack &top, Box end, Box temp)
{
    int current_x, current_y, current_di; // 当前坐标
    int next_x, next_y;                   // 下一个位置的坐标
    maze[temp.current_y][temp.current_x] = -1;
    push(top, temp);
    while (!isEmpty(top))
    {
        temp = pop(top);
        current_x = temp.current_x;
        current_y = temp.current_y;
        current_di = temp.di + 1;
        while (current_di < 4)
        {
            next_x = current_x + direction[current_di][0]; // 确定下个位置的x坐标
            next_y = current_y + direction[current_di][1]; // 确定下个位置的y坐标

            if (maze[next_y][next_x] == 0)
            { // 判断下个位置坐标是否可走
                maze[next_y][next_x] = -1;
                temp.current_x = current_x;
                temp.current_y = current_y;
                temp.di = current_di; // 将当前方向保存
                push(top, temp);      // 入栈
                // print_maze(maze);
                current_x = next_x; // 更新坐标
                current_y = next_y; // 更新坐标
                current_di = 0;
                if (current_x == end.current_x && current_y == end.current_y)
                { // 到达终点
                    temp.current_x = current_x;
                    temp.current_y = current_y;
                    temp.di = current_di; // 将当前方向保存
                    push(top, temp);      // 入栈
                    return true;
                }
            }
            else
            {
                current_di++; // 更换方向
            }
        }
        if (current_di == 4 && maze[current_y][current_x] == -1) // 当前坐标已走完且无通路
        {
            maze[current_y][current_x] = -2;
        }
    }
    return false;
}
void RecursionDFS(int maze[M][N], int direction[][2], Linkstack &top, Box current, Box end)
{
    if (current.current_x == end.current_x && current.current_y == end.current_y)
    {
        printf("这是一条路径\n");
        print_stack(top);
        print_maze(maze);
        printf("============================\n");
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        if (maze[current.current_y][current.current_x] == 0)
        { // 将起点进栈
            maze[current.current_y][current.current_x] = -1;
        }

        int next_x = current.current_x + direction[i][0];
        int next_y = current.current_y + direction[i][1];
        if (maze[next_y][next_x] == 0)
        {

            maze[next_y][next_x] = -1;
            Box temp;
            temp.current_x = next_x;
            temp.current_y = next_y;
            current.di = i;                                //!!!!!!!,记录当前要存入栈中位置的指向下一个位置的方向
            push(top, current);                            // 存入当前位置，以及当前指向下一个位置的方向
            RecursionDFS(maze, direction, top, temp, end); // 传入的temp是自己本身的坐标，不是下一个位置的坐标
            maze[next_y][next_x] = 0;
            pop(top);
        }
    }
}
int main()
{
    Linkstack top = NULL;
    int direction[][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // 方位数组，上右下左
    int maze[M][N] = {                                       // 测试案例1，M，N都为10
                      {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                      {1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
                      {1, 0, 1, 1, 1, 1, 1, 1, 1, 1},
                      {1, 0, 1, 0, 0, 0, 0, 0, 0, 1},
                      {1, 0, 0, 0, 1, 1, 1, 1, 0, 1},
                      {1, 0, 1, 0, 1, 0, 0, 0, 0, 1},
                      {1, 0, 1, 0, 1, 1, 1, 1, 0, 1},
                      {1, 0, 1, 0, 0, 0, 0, 0, 0, 1},
                      {1, 1, 1, 1, 1, 1, 1, 1, 0, 1},
                      {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};
    //       int maze[M][N] = {                                       // 测试案例2，M，N都为10，无通路
    //   {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    //   {1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    //   {1, 0, 1, 1, 1, 1, 1, 1, 1, 1},
    //   {1, 0, 1, 0, 0, 0, 0, 0, 0, 1},
    //   {1, 0, 0, 0, 1, 1, 1, 1, 0, 1},
    //   {1, 0, 1, 0, 1, 0, 0, 0, 0, 1},
    //   {1, 0, 1, 0, 1, 1, 1, 1, 1, 1},
    //   {1, 0, 1, 1, 0, 0, 0, 0, 0, 1},
    //   {1, 1, 1, 1, 1, 1, 1, 1, 0, 1},
    //   {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};
    // int maze[M][N] = {
    //     {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, // 测试案例3，M，N都为12
    //     {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    //     {1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1},
    //     {1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1},
    //     {1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1},
    //     {1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1},
    //     {1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1},
    //     {1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
    //     {1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1},
    //     {1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1},
    //     {1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1},
    //     {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};
    bool is = DFS(maze, direction, top, Box{8, 8, 0}, Box{1, 1, -1}); // 测试案例1
    // bool is = DFS(maze, direction, top, Box{8, 8, 0}, Box{1,1,-1});//测试案例2
    // bool is = DFS(maze, direction, top, Box{10, 10, 0}, Box{1, 1, -1});//测试案例3
    if (is)
    {
        printf("找到路径\n");
        print_stack(top);
        print_maze(maze);
    }
    else
    {
        printf("没有找到路径\n");
    }
    // RecursionDFS(maze, direction, top, Box{1, 1, 0}, Box{8, 8, 0}); // 递归求全路径，测试案例1，2
    //    RecursionDFS(maze, direction, top, Box{1, 1, 0}, Box{8, 8, 0}); // 递归求全路径，测试案例1，2
    // RecursionDFS(maze, direction, top, Box{1, 1, 0}, Box{10, 10, 0}); // 递归求全路径，测试案例3
    return 0;
}