问题描述：
有一个迷宫地图，有一些可达的位置，也有一些不可达的位置（障碍、墙壁、边界）。从一个位置到下一个位置只能通过向上（或者向右、或者向下、或者向左）走一步来实现，从起点出发，找到任何可以到达出口的路径并输出，最后输出最短路径以及最短路径长度。
用二维矩阵来模拟迷宫地图，1代表该位置不可达，0代表该位置可达。每走过一个位置就将地图的对应位置标记，以免重复。
以下是源代码：
迷宫.cpp:
#include"迷宫1.h" int main() { cout << "该迷宫为：" << endl; for (int i = 1; i <= 8; i++) { //输出迷宫 for (int j = 1; j <= 8; j++) { cout << mg[i][j] << " "; } cout << endl; } if (!mgpath(1, 1, 8, 8)) //迷宫没有路 cout<<"该迷宫没有出路!"<<endl; return 0; }
迷宫1.h:
#pragma once #include"迷宫函数.h" void InitStack(SqStack*& s);//初始化栈 int Push(SqStack*& s, Box e);//进栈 bool StackEmpty(SqStack* s);//判断栈是否为空 bool Pop(SqStack*& s, Box& e);//出栈 bool GetTop(SqStack* s, Box& e);//取出栈顶元素 bool mgpath(int xi, int yi, int xe, int ye);//入口出口分别为(xi,yi)(xe,ye)
迷宫函数.h：
#pragma once #pragma once #include <iostream> using namespace std; #define inf 0x3f3f3f //表示无穷 const int MaxSize = 1000;//顺序栈存储空间的初始分配量 int M = 8, N = 8;//出口 int mg[10][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,0,0,1,1,0,1}, {1,0,0,0,1,0,0,1,0,1}, {1,1,0,0,0,1,0,1,0,1}, {1,1,0,0,0,1,0,0,0,1}, {1,1,0,0,0,1,0,0,0,1}, {1,1,0,0,0,1,1,1,0,1}, {1,1,0,0,0,1,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} }; int vis[10][10];//表示该点是否走过 typedef struct { int i;//当前方块的行号 int j;//当前方块的列号 int di;//方向 }Box; typedef struct { Box data[MaxSize]; int top;//整型栈顶指针 }SqStack;//顺序栈类型 void InitStack(SqStack*& s)//初始化栈 { s = (SqStack*)malloc(sizeof(SqStack));//动态分配内存 s->top = -1; } int Push(SqStack*& s, Box e)//进栈 { if (s->top == MaxSize - 1) return -1;//栈满 s->top++; s->data[s->top] = e;//e压入栈顶 } bool StackEmpty(SqStack* s)//判断栈是否为空 { if (s->top == -1); return (s->top == -1); } bool Pop(SqStack*& s, Box& e)//出栈 { if (s->top == -1) return false; e = s->data[s->top];//栈顶元素赋给e s->top--;//栈顶指针-1 return true; } bool GetTop(SqStack* s, Box& e)//取出栈顶元素 { if (s->top == -1) return false; e = s->data[s->top]; return true; } bool mgpath(int xi, int yi, int xe, int ye)//入口出口分别为(xi,yi)(xe,ye) { int minl = inf;//路径长度 int minr;//路径 int cont = 1;//初始化路径为1 int f = 0; int i, j, di, i1, j1, k;//方向 bool _find = false;//表示方块是否探索过 SqStack* st;//定义栈st InitStack(st);//初始化栈st Box e1, e;//定义方块e1,e e1.i = xi;//入口行号 e1.j = yi;//入口列号 e1.di = -1; Push(st, e1);//方块e进栈 vis[xi][yi] = -1;//将入口的迷宫值置为-1,避免重复走到该方块 while (!StackEmpty(st))//栈不为空时循环 { GetTop(st, e); i = e.i;//方块行号 j = e.j;//方块列号 int a = 0; int b = 0; di = e.di; char mg1[10][10];//用于复制mg矩阵 for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { mg1[i][j] = mg[i][j]; } } if (i == xe && j == ye)//找到了出口,输出该路径 { f = 1; if (st->top < minl) { minl = st->top;//路径长度 minr = cont; } cout << "迷宫路径" << cont++ << "为："; for (k = 0; k <= st->top; k++) { cout << ">(" << st->data[k].i << "," << st->data[k].j << ")"; for (a = 1; a <= 8; a++) {//记录走过的位置 for (b = 1; b <= 8; b++) { if ((a == st->data[k].i) && (b == st->data[k].j)) { mg1[a][b] = '*'; } } } } cout << endl; cout << "*表示走过的路径，移动轨迹为：" << endl; for (a = 1; a <= 8; a++) {//输出移动轨迹 for (b = 1; b <= 8; b++) { cout << mg1[a][b] << " "; } cout << endl; } } _find = false; while (di < 8 && !_find)//该路不通 { di++; switch (di)//上下左右四个方向探索 { case 0:i1 = i - 1; j1 = j; break; case 1:i1 = i; j1 = j + 1; break; case 2:i1 = i + 1; j1 = j; break; case 3:i1 = i; j1 = j - 1; break; } if (vis[i1][j1] == 0 && mg[i1][j1] == 0) _find = true;//找到路 } if (_find) //此方块可行 { st->data[st->top].di = di; e.i = i1; e.j = j1; e.di = -1; Push(st, e); //进栈 vis[i1][j1] = -1;//将该点的迷宫值置为-1,避免重复走到该方块 } else { Pop(st, e); //出栈 vis[e.i][e.j] = 0;//将迷宫值重新置为0 } } if (f == 1) { cout << "最短路径为路径" << minr << endl; cout << "最短路径长度为" << minl << endl; return true; } return false; }
