阅读:0       作者:严长生

数据结构实践项目之移动迷宫小游戏(升级版)

在上一章的《移动迷宫》小游戏中,使用回溯法帮助骑士在迷宫中找到了通往出口的一条通路,但是骑士并不太满意,他又提出了更高的需求。

《移动迷宫》升级版游戏简介:迷宫只有两个门,一个入口,一个出口。一个骑士骑马从入口走进迷宫,迷宫中设置有很多墙壁,对前进方向造成障碍。先需要你从迷宫中找到一条最短的通路,将行走路线和行走的最短距离告知骑士。

设计思路

类似于寻找最短路径这样的问题,最直接的方法就是使用迪杰斯特拉算法弗洛伊德算法

两种算法面对的数据结构是图,但是迷宫是在二维数组中进行存储的,所以如果使用前面两种算法的话,需要首先将二维数组转化为图的存储形式。

二维数组转化成图

如下图所示,此为 3*3 迷宫:


图 1 移动迷宫

提示:S 为入口,E 为出口,# 为墙壁,- 为通路。

在编写程序向计算机中输入该迷宫的数据时,宜使用二维数组进行存储。但是无论是迪杰斯特拉算法还是弗洛伊德算法,其处理对象都是有向网或者无向网。迷宫中并不涉及到具体的方向,所以需要将存储迷宫的二维数组转化为无向网。

无向网的存储方式也是用二维数组来实现,将迷宫中所有的顶点看作是图中的顶点,对于上图的迷宫来说,共有 9 个顶点,所以转化为无向网时,需要用 9*9 的一个二维数组来表示。

在转化时,从迷宫的左上角(上图的 S 开始),一行一行的进行转化,对于每个顶点来说,只需要判断其右侧和相邻的下方顶点是否为通路,如果是通路,转化为图中的直接体现就是两顶点之间有线连接。

例如,上图中的 S 其右侧和下方的顶点都是 - ,骑士可以通过,那在图中的表现就是 S 同其右侧顶点和下方顶点之间存储通路,如下图所示:
对于图 1 中的二维数组,其完全转化为图,如下图所示(每个顶点用其二维数组中的坐标来表示,00 表示第 0 行第 0 列):
图 1 中的二维数组转化为图的存储表示如下图所示:

提示:1 表示有通路,0 表示没有通路,# 由于表示墙壁,同其它任何顶点之间都没有通路。

迪杰斯特拉算法

使用迪杰斯特拉算法求迷宫的最短路径,其完整代码如下:
#include <stdio.h>
#define MAX_VERtEX_NUM 1000              //顶点的最大个数
#define VRType int                          //表示弧的权值的类型
#define VertexType char                     //图中顶点的数据类型
#define INFINITY 65535
typedef enum{false,true} bool;
typedef struct {
    VertexType vexs[MAX_VERtEX_NUM];        //存储图中顶点数据
    VRType arcs[MAX_VERtEX_NUM][MAX_VERtEX_NUM];                         //二维数组,记录顶点之间的关系
    int vexnum,arcnum;                      //记录图的顶点数和弧(边)数
}MGraph;
typedef int PathMatrix[MAX_VERtEX_NUM];     //用于存储最短路径中经过的顶点的下标
typedef int ShortPathTable[MAX_VERtEX_NUM]; //用于存储各个最短路径的权值和

//迪杰斯特拉算法,v0表示有向网中起始点所在数组中的下标
void ShortestPath_Dijkstra(MGraph G,int v0,PathMatrix *p,ShortPathTable *D){
    int final[MAX_VERtEX_NUM];//用于存储各顶点是否已经确定最短路径的数组
    //对各数组进行初始化
    for (int v=0; v<G.vexnum; v++) {
        final[v]=0;
        (*D)[v]=G.arcs[v0][v];
        (*p)[v]=0;
    }
    //以起点为下标的顶点为起始点,所以不用再判断
    (*D)[v0]=0;
    final[v0]=1;
    int k = 0;
    for (int i=0; i<G.vexnum; i++) {
        int min=INFINITY;
        //选择到各顶点权值最小的顶点,即为本次能确定最短路径的顶点
        for (int w=0; w<G.vexnum; w++) {
            if (!final[w]) {
                if ((*D)[w]<min) {
                    k=w;
                    min=(*D)[w];
                }
            }
        }
        //设置该顶点的标志位为1,避免下次重复判断
        final[k]=1;
        //对从起点到各顶点的权值进行更新
        for (int w=0; w<G.vexnum; w++) {
            if (!final[w]&&(min+G.arcs[k][w]<(*D)[w])) {
                (*D)[w]=min+G.arcs[k][w];
                (*p)[w]=k;//记录各个最短路径上存在的顶点
            }
        }
    }
}
//在将二维数组转化为图的过程中,需要判断当前的点是否越界或者是否为通路
bool canUsed(int i,int j,int n,int m,char a[][110]){
    if (a[i][j]!='#' && i>=0 && i<n && j>=0 && j<m) {
        return true;
    }
    return false;
}
int main(){
    char a[110][110];
    int n,m;
    scanf("%d %d",&n,&m);
    getchar();
    MGraph G;
    G.vexnum=0;
    G.arcnum=0;
    //记录入口在图的顶点数组中的位置下标
    int start =0;
    //记录出口在图的顶点数组中的位置下标
    int exit=0;
    //初始化记录图的边的二维数组,假设各个边的长度为无穷大,即两顶点之间没有边
    for (int i=0; i<n*m; i++) {
        for (int j=0; j<n*m; j++) {
            G.arcs[i][j]=INFINITY;
        }
    }
    //输入二维数组,同时记录入口和出口的位置
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            scanf("%c",&a[i][j]);
            G.vexs[i*m+j]=a[i][j];
            G.vexnum++;
            if (a[i]
                [j]=='S') {
                start=i*m+j;
            }else if(a[i][j]=='E'){
                exit=i*m+j;
            }
        }
        getchar();//作用是为了读取缓存区中的换行符(因为迷宫是一行一行输入到内存中的)
    }
    //将二维数组转换为无向图,在转换时,从二维数组的左上角开始,每次判断当前顶点的右侧和下侧是否为通路,这样所有的通路就可以转换为无向图中的边。
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            //首先判断当前点是否为通路
            if (canUsed(i, j, n, m, a)) {
                if (canUsed(i+1, j, n, m, a)) {
                    //设定两顶点之间的边的权值为 1
                    G.arcs[i*m+j][(i+1)*m+j]=1;
                    G.arcs[(i+1)*m+j][i*m+j]=1;
                    G.arcnum++;
                }
                if (canUsed(i, j+1, n, m, a)) {
                    G.arcs[i*m+j][i*m+j+1]=1;
                    G.arcs[i*m+j+1][i*m+j]=1;
                    G.arcnum++;
                }
            }
        }
    }
    PathMatrix P;
    ShortPathTable D;
    //进行迪杰斯特拉算法
    ShortestPath_Dijkstra(G,start, &P, &D);
    //如果最终记录的权值和还是无穷大,证明,入口和出口之间没有通路
    if (D[exit]==INFINITY) {
        printf("-1");
    }else{
        printf("入口到出口的最短路径长度为:\n");
        printf("%d\n",D[exit]);
        printf("入口到出口的最短路径为(逆序):\n");
        printf("(%d,%d) ",exit/m,exit%m);
        while (P[exit]!=0) {
            printf("(%d,%d) ",P[exit]/m,P[exit]%m);
            exit=P[exit];
        }
        printf("(%d,%d)\n",start/m,start%m);
    }
    return 0;
}
运行结果:
程序输入:
3 3
S-#
---
##E
程序输出:
入口到出口的最短路径长度为:
4
入口到出口的最短路径为(逆序):
(2,2) (1,2) (1,1) (0,1) (0,0)

广度优先搜索解决最短路径问题

除了以上两种可以称得上是直接求最短路径的方法,还可以应用本章的广度优先搜索算法查找最短路径,该算法的实现可以直接在二维数组中完成,没有必要转化为图的形式。
例如拿上图中的迷宫举例,骑士一开始只能选择向右走,当走到坐标为 (2,2) 的位置,骑士有两个选择:向上走或者向下走。

对于广度优先搜索来说,其实现使用的数据存储结构为队列,在搜索的过程中,将每种可选情况都入队,然后一轮一轮的对队列中的可选情况进行尝试,知道尝试出想要的结果为止。

对于此时的骑士来说,结合对广度优先算法的理解,就相当于骑士会分身术,一分为二,一个往上,一个往下,每个人每次只能走一步(你走一步然后我走一步)。

例如假设骑士走下,分身去上,当骑士走到坐标为(3,4)的位置时,又需要选择,要么往右,要么往下,此时骑士又分身,各走各的。但是无论怎么分,所有的骑士都是每次只走一步。

在这种情况下,当只要有一个骑士找到出口时,他所走的路径就绝对是最短路径。

对于广度优先搜索来说,使用的是队列的数据结构,等同于在遍历一棵二叉树时,一层一层的遍历(从上往下,从左往右),可以看做是,对于每种情况,轮流去试探,每次只走一步。

在实际编程实现时,使用广度优先搜索查找最短路径时,只能求得最短路径的长度,如果想要获取最短路径的具体路线,还需要结合其他算法。

在本节,给大家的一个解决思路是:在存储迷宫时,对于每个顶点都分配一个整形变量,在进行广度优先搜索时,骑士和其分身每走一步,该顶点所携带的整形变量的值都是骑士之前所处位置的整形变量+1。

例如,对于下图的迷宫来说,骑士在最终找到出口时的整形变量为:


 

提示:从入口开始,初始值假设为 0 ,其右侧通路和下方通路的整形变量的值是0+1=1,最终其出口自身所携带的整形变量值就是最短路径的长度。

通过对“骑士们”所走路线中整形变量的设置,此时我们可以结合回溯法,从入口开始寻找骑士所可能走的所有的最短路径(此时找到的可能不只有一条)。

在使用回溯法时,从入口出发,每次同当前顶点周围查找比自身整形变量值大 1 的顶点,就是骑士所走的路线。如果找不到,回退再找,直到将所有的情况都试探完。

广度优先搜索+回溯法解决移动迷宫问题的完整代码为:
#include <stdio.h>
typedef enum{false,true} bool;

typedef struct {
    int x;
    int y;
    char mess;
    int value;
}check;

bool canUsed(int x,int y,char data,int n,int m){
    if (x>=0 && x<n && y>=0 && y<m && data!='#') {
        return true;
    }
    return false;
}
void createMaze(int n,int m,check a[][110],int *entryx,int *entryy,int *exitx,int *exity){
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            scanf("%c",&a[i][j].mess);
            a[i][j].x=i;
            a[i][j].y=j;
            if (a[i][j].mess=='S') {
                *entryx=i;
                *entryy=j;
            }else if(a[i][j].mess=='E'){
                *exitx=i;
                *exity=j;
            }
        }
        getchar();
    }
}
//使用的广度优先搜索的思想,采用队列的数据结构实现
void findRoad(check a[][110],int top,int rear,check queue[],int *value,int entryx,int entryy,int n,int m){
    //首先将入口顶点入队
    check data;
    data.x=entryx;
    data.y=entryy;
    a[entryx][entryy].mess='#';
    data.mess=a[entryx][entryy].mess;
    data.value=0;
    queue[rear]=data;
    bool success=false;
    rear++;
    //队列不满
    while (top!=rear) {
        //逐个出队
        check temp=queue[top];
        a[temp.x][temp.y].value=temp.value;
        top++;
        //对于出队的顶点判断是否是出口,首个判断为出口的顶点,其value值就是最短路径的长度
        if (temp.mess=='E') {
            *value=temp.value;
            printf("%d\n",temp.value);
            success=true;
            break;
        }
        //每次入队,判断其上、下、左、右的顶点是否符合条件,若符合,则入队,同时对其value值赋值为前一个顶点value+1,为了避免重复判断此顶点,对每个入队的顶点,设定其字符为‘#’
        if(canUsed(temp.x-1,temp.y,a[temp.x-1][temp.y].mess,n,m)){
            data.x=temp.x-1;
            data.y=temp.y;
            data.mess=a[temp.x-1][temp.y].mess;
            data.value=temp.value+1;
            queue[rear]=data;
            a[temp.x-1][temp.y].mess='#';
            rear++;
        }
        //右边
        if(canUsed(temp.x,temp.y+1,a[temp.x][temp.y+1].mess,n,m)){
            data.x=temp.x;
            data.y=temp.y+1;
            data.mess=a[temp.x][temp.y+1].mess;
            data.value=temp.value+1;
            queue[rear]=data;
            a[temp.x][temp.y+1].mess='#';
            rear++;
        }
        //下边
        if(canUsed(temp.x+1,temp.y,a[temp.x+1][temp.y].mess,n,m)){
            data.x=temp.x+1;
            data.y=temp.y;
            data.mess=a[temp.x+1][temp.y].mess;
            data.value=temp.value+1;
            queue[rear]=data;
            a[temp.x+1][temp.y].mess='#';
            rear++;
        }
        //左边
        if(canUsed(temp.x,temp.y-1,a[temp.x][temp.y-1].mess,n,m)){
            data.x=temp.x;
            data.y=temp.y-1;
            data.mess=a[temp.x][temp.y-1].mess;
            data.value=temp.value+1;
            queue[rear]=data;
            a[temp.x][temp.y-1].mess='#';
            rear++;
        }
    }
    //如果不成功,证明出口和入口之间没有通路
    if (success==false) {
        printf("-1\n");
    }
}
//用于输出最短路径时回溯过程中的判断
bool judgeValue(int x,int y,int n,int m){
    if (x>=0 && x<n && y>=0 && y<m ){
        return true;
    }
    return false;
}
//在输出时,由于最短路径中从入口开始,一直到出口,所经过的顶点的 value 值逐渐 +1,所以采用回溯法查找所有可能的最短路径
void displayRoad(check a[][110],int entryx,int entryy,int n,int m,int value){
    //设置静态数组,实现栈的作用
    static check stack[1000];
    static int top=-1;//栈的栈顶
    //对于每个当前的顶点,首先需要判断其是否符合最基本的要求,由于在前期二维数组中的通路都变成了‘#’,这里采用另一个关键字 ,value的值为主关键字进行搜索
    if (judgeValue(entryx, entryy, n, m)) {
        //回溯思想的实现用的是递归,所以需要设置一个出口,出口就是当查找到顶点的value值为最短路径的顶点数时,表明此时已经搜索在出口位置,此时就可以依次输出栈内存储的各个经过的顶点的坐标
        if (a[entryx][entryy].value==value) {
            for (int i=0; i<top; i++) {
                printf("(%d,%d) ",stack[i].x,stack[i].y);
            }
            printf("\n");
            return;
        }
        //从入口出发,判断当前点的上、下、左、右位置上的顶点是否符合要求:1、该顶点的坐标没有超出范围;2该顶点的value值是前一个顶点的value值+1,如果都符合,说明之前判断最短路径时就途径此顶点,将其入栈进行保存
        if (judgeValue(entryx+1, entryy, n, m) && a[entryx+1][entryy].value==a[entryx][entryy].value+1) {
            top++;
            stack[top]=a[entryx+1][entryy];
            displayRoad(a, entryx+1, entryy, n, m,value);
            //当运行至此,又两种情况:途径此顶点最终找到出口,并将最终结果输出,此时应将该顶点弹栈;该顶点的路径不是正确的,应弹栈。两种情况都应弹栈。
            top--;
        }
        if (judgeValue(entryx-1, entryy, n, m) && a[entryx-1][entryy].value==a[entryx][entryy].value+1) {
            top++;
            stack[top]=a[entryx-1][entryy];
            displayRoad(a, entryx-1, entryy, n, m,value);
            top--;
        }
        if (judgeValue(entryx, entryy+1, n, m) && a[entryx][entryy+1].value==a[entryx][entryy].value+1) {
            top++;
            stack[top]=a[entryx][entryy+1];
            displayRoad(a, entryx, entryy+1, n, m,value);
            top--;
        }
        if (judgeValue(entryx, entryy-1, n, m) && a[entryx][entryy-1].value==a[entryx][entryy].value+1) {
            top++;
            stack[top]=a[entryx][entryy-1];
            displayRoad(a, entryx, entryy-1, n, m,value);
            top--;
        }
    }
}
int main(int argc, const char * argv[]) {
    check a[110][110];
    check queue[100000];
    int top=0,rear=0;   
    int n,m;
    int entryx = 0,entryy=0,exitx=0,exity=0;
    scanf("%d %d",&n,&m);
    getchar();
    //创建迷宫,并找到入口和出口的位置坐标
    createMaze(n,m,a,&entryx,&entryy,&exitx,&exity);
    //在迷宫中查找从入口到出口的最短路径,若有,输出最短路径的长度;反之,输出-1
    int value;
    findRoad(a,top,rear,queue,&value,entryx,entryy,n,m);
    //输出所有的最短路径
    displayRoad(a, entryx, entryy, n, m, value);
    return 0;
}
运行结果:
输入部分:
3 3
S-#
---
#-E
4
程序输出部分:
(1,0) (1,1) (2,1)
(1,0) (1,1) (1,2)
(0,1) (1,1) (2,1)
(0,1) (1,1) (1,2)

提示:通过对通路进行整体的回溯,可以找到所有可能的结果,这个例子中,有四条长度相同的最短路径。

总结

本节主要解决的是求有关点到点的最短路径的问题,其问题的解决既可以使用“专业工具” -- 迪杰斯特拉算法和弗洛伊德算法,也有“组合套装” -- 广度优先搜索 + 回溯法。通过这个项目,大家要学会将所学的知识融会贯通,综合运用。