数据结构与算法——第6章-树-移动迷宫小游戏(6.21)

发表于 2023-04-07 分类于开发， N-数据与算法，数据结构与算法阅读时长 ≈ 5 分钟

一概述

1.游戏介绍
2.设计思路
3.实例分析
4.示例代码

二游戏介绍

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

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

三设计思路

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

通过不停地对可行道路进行试探，结果有两种：
1.骑士最终找到了一条通往出口的道路；
2.试探结束，没有通往出口的道路，骑士最终只能被迫返回入口，继续等到迷宫的下一次变化（程序结束）。

四实例分析

一、迷宫介绍

1
2

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

二、骑士探索

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

通过骑士不断地探索，对于该实例中列举的迷宫，骑士最终可以找到一条通往出口的道路，如下图所示：
提示：迷宫中，新增的‘X’表示骑士走过的道路（找出一条通路即可）。

五示例代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef enum {false,true} bool;
//迷宫本身是一个8行10列的矩形
int ROWS=8;
int COLS=10;
//初始化迷宫，随机设置迷宫出入口，同时在迷宫中随机设置可行道路。
void mazeGenerator(char [][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[][COLS]);
//判断每一次移动是否有效
bool validMove(const char [][COLS],int,int);

int main()
{
    printf("*********移动迷宫小项目（数据结构就该这么学）*********\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[][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[][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[][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 递归回忆：
比如说你在面对一个二叉路口，不知道要走哪条，此时就要做尝试（尝试这个动作就是一个函数）你选择先尝试左边这条，
往左边走，走着走着发现又有一个二叉路口，此时你需要上一次尝试的过程中要再做一次尝试，
即在函数内再调用一次函数，这是递归。但是如果你发现这条路走不通，就知道上一个二岔路你选择错了，
此时你回到原来的岔路口选择右边，这就是回溯（回溯使用递归的思想实现的一种算法结构）。

七参考

C语言中文网—移动迷宫小游戏(初级版)

0%