[数据结构实践项目]移动迷宫小游戏(初级版)

《移动迷宫》游戏简介：迷宫只有两个门，一个入口，一个出口。一个骑士骑马从入口走进迷宫，迷宫中设置有很多墙壁，对前进方向造成障碍。骑士需要在迷宫中寻找通路以到达出口。

本游戏的迷宫是“移动”的，每次骑士进入迷宫时，迷宫的入口、出口，甚至是迷宫中设置的障碍都是不同的。

设计思路

解决类似的问题，使用回溯法是最行之有效的解题方法。骑士从入口开始，不断地对周围的道路进行试探：若能走通，则进入该位置，继续对周围进行试探；反之，则后退一步，继续寻求其他的可行路径。

通过不停地对可行道路进行试探，结果有两种：

• 骑士最终找到了一条通往出口的道路；
• 试探结束，没有通往出口的道路，骑士最终只能被迫返回入口，继续等到迷宫的下一次变化（程序结束）。

实例分析

假设迷宫为一块长为 10 ，宽为 8 的矩形区域，其中随机设置了入口、出口和该区域内可供通行的道路，如下图所示：

提示：迷宫中，‘0’ 表示道路，‘#’ 表示障碍。

当骑士处于入口的位置时，他会前后左右的进行探索式前进，当他发现前方道路可行时，即坐标为（2，1）的通路，此时骑士会快速移动至该位置，进行以该位置为中心的再次探索式前进。

通过骑士不断地探索，对于该实例中列举的迷宫，骑士最终可以找到一条通往出口的道路，如下图所示：

提示：迷宫中，新增的‘X’表示骑士走过的道路（找出一条通路即可）。

完整实现代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef enum { false, true } bool;
//迷宫本身是一个8行10列的矩形
#define ROWS 8
#define COLS 10
//初始化迷宫，随机设置迷宫出入口，同时在迷宫中随机设置可行道路。
void mazeGenerator(char maze[ROWS][COLS], int *, int *, int *, int *);
//使用回溯法从入口处不断地尝试找到出口的路径
void mazeTraversal(char maze[ROWS][COLS], int row, int col, int entryRow, int entryCol, int exitrow, int exitcol);
//迷宫的输出函数
void printMaze(const char maze[ROWS][COLS]);
//判断每一次移动是否有效
bool validMove(const char maze[ROWS][COLS], int, int);
int main()
{
    printf("*********移动迷宫小项目（http://www.cdsy.xyz）*********\n");
    char maze[ROWS][COLS];
    int xStart, yStart, x, y;
    srand(time(0));//种下随机种子数，每次运行种下不同的种子，后序通过rand()函数获得的随机数就不同。
    //通过一个嵌套循环，先将迷宫中各个地方设置为死路(‘#’表示为墙，表示此处不可通过)
    for (int loop = 0; loop < ROWS; ++loop) {
        for (int loop2 = 0; loop2 < COLS; ++loop2) {
            maze[loop][loop2] = '#';
        }
    }
    //初始化迷宫，即在迷宫中随机设置出口、入口和中间的道路，用‘0’表示。通过此函数，可同时得到入口的坐标
    mazeGenerator(maze, &xStart, &yStart, &x, &y);
    printf("迷宫入口位置坐标为(%d,%d);出口位置坐标为：(%d，%d);\n", xStart + 1, yStart + 1, x + 1, y + 1);
    printf("迷宫设置如下（‘#’表示墙，‘0’表示通路）：\n");
    printMaze(maze);//输出一个初始化好的迷宫
    //使用回溯法，通过不断地进行尝试，试图找到一条通往出口的路。
    mazeTraversal(maze, xStart, yStart, xStart, yStart, x, y);
}
//由于迷宫整体布局为矩形，有四条边，在初始化迷宫的出口和入口时，随机选择不同的两条边作为设置出口和入口的边
void mazeGenerator(char maze[ROWS][COLS], int *xPtr, int *yPtr, int *exitx, int *exity) {
    int a, x, y, entry, exit;
    do {
        entry = rand() % 4;
        exit = rand() % 4;
    } while (entry == exit);
    // 确定入口位置，0 代表选择的为左侧的边，1 代表为上边，2代表为右侧的边，3 代表为下边
    if (entry == 0) {
        *xPtr = 1 + rand() % (ROWS - 2);
        *yPtr = 0;
        maze[*xPtr][*yPtr] = '0';
    }
    else if (entry == 1) {
        *xPtr = 0;
        *yPtr = 1 + rand() % (COLS - 2);
        maze[*xPtr][*yPtr] = '0';
    }
    else if (entry == 2) {
        *xPtr = 1 + rand() % (ROWS - 2);
        *yPtr = COLS - 1;
        maze[*xPtr][*yPtr] = '0';
    }
    else {
        *xPtr = ROWS - 1;
        *yPtr = 1 + rand() % (COLS - 2);
        maze[*xPtr][*yPtr] = '0';
    }
    //确定出口位置
    if (exit == 0) {
        a = 1 + rand() % (ROWS - 2);
        *exitx = a;
        *exity = 0;
        maze[a][0] = '0';
    }
    else if (exit == 1) {
        a = 1 + rand() % (COLS - 2);
        *exitx = 0;
        *exity = a;
        maze[0][a] = '0';
    }
    else if (exit == 2) {
        a = 1 + rand() % (ROWS - 2);
        *exitx = a;
        *exity = COLS - 1;
        maze[a][COLS - 1] = '0';
    }
    else {
        a = 1 + rand() % (COLS - 2);
        *exitx = ROWS - 1;
        *exity = a;
        maze[ROWS - 1][a] = '0';
    }
    //在迷宫中央设置多出不同的随机通路
    for (int loop = 1; loop < (ROWS - 2)*(COLS - 2); ++loop) {
        x = 1 + rand() % (ROWS - 2);
        y = 1 + rand() % (COLS - 2);
        maze[x][y] = '0';
    }
}
void mazeTraversal(char maze[ROWS][COLS], int row, int col, int entryRow, int entryCol, int exitrow, int exitcol) {
    //由于从入口处进入，为了区分走过的通路和没走过的通路，将走过的通路设置为‘x’，
    maze[row][col] = 'x';
    static bool judge = false;//设置一个判断变量，判断在入口位置是否有通路存在。
    static int succ = 0;//用于统计从入口到出口的可行通路的条数
    if (row == exitrow && col == exitcol) {
        printf("成功走出迷宫，道路图如下：\n");
        printMaze(maze);
        succ++;
        return;
    }
    //判断当前位置的下方是否为通路
    if (validMove(maze, row + 1, col)) {
        judge = true;//证明起码有路存在，下面证明是否有可通往出口的路
        mazeTraversal(maze, row + 1, col, entryRow, entryCol, exitrow, exitcol);//以下方的位置为起点继续尝试
    }
    //判断当前位置的右侧是否为通路
    if (validMove(maze, row, col + 1)) {
        judge = true;
        mazeTraversal(maze, row, col + 1, entryRow, entryCol, exitrow, exitcol);
    }
    //判断当前位置的上方是否为通路
    if (validMove(maze, row - 1, col)) {
        judge = true;
        mazeTraversal(maze, row - 1, col, entryRow, entryCol, exitrow, exitcol);
    }
    //判断当前位置的左侧是否为通路
    if (validMove(maze, row, col - 1)) {
        judge = true;
        mazeTraversal(maze, row, col - 1, entryRow, entryCol, exitrow, exitcol);
    }
    //如果judge仍为假，说明在入口处全部被墙包围，无路可走
    if (judge == false) {
        printf("入口被封死，根本无路可走！\n");
        printMaze(maze);
    }
    //如果judge为真，但是succ值为0，且最终又回到了入口的位置，证明所有的尝试工作都已完成，但是没有发现通往出口的路
    else if (judge == true && row == entryRow && col == entryCol && succ == 0) {
        printf("尝试了所有道路，出口和入口之间没有通路！\n");
        printMaze(maze);
    }
}
//有效移动，即证明该位置处于整个迷宫的矩形范围内，且该位置是通路，不是墙，也从未走过
bool validMove(const char maze[ROWS][COLS], int r, int c) {
    return(r >= 0 && r <= ROWS - 1 && c >= 0 && c <= COLS - 1 && maze[r][c] != '#'&& maze[r][c] != 'x');
}
//输出迷宫
void printMaze(const char maze[ROWS][COLS]) {
    for (int x = 0; x < ROWS; ++x) {
        for (int y = 0; y < COLS; ++y) {
            printf("%c ", maze[x][y]);
        }
        printf("\n");
    }
    printf("\n");
}

该程序由于每次运行产生不同的迷宫，所以每次运行结果不同，可自行运行，查看结果，这里不再进行描述。

总结

通过练习《移动迷宫》小游戏，旨在让大家熟悉回溯法的解题思路。

回溯 PK 递归回忆：比如说你在面对一个二叉路口，不知道要走哪条，此时就要做尝试（尝试这个动作就是一个函数）你选择先尝试左边这条，往左边走，走着走着发现又有一个二叉路口，此时你需要上一次尝试的过程中要再做一次尝试，即在函数内再调用一次函数，这是递归。但是如果你发现这条路走不通，就知道上一个二岔路你选择错了，此时你回到原来的岔路口选择右边，这就是回溯（回溯使用递归的思想实现的一种算法结构）。