C语言 迷宫求解 严蔚敏 数据结构 可视化界面-课程作业
题目数据结构课程，讲完栈，老师留下严蔚敏PPT上的作业，迷宫求解，如下：解题思路1）采用递归的深度优先搜索，从出发点搜索至结束点2）递归中自带“栈特性”，在进入当前递归函数相当于栈的push，退出当前递归函数相当于栈的pop，那么根据这个特性，实现搜索地图中返回上一个结点的功能。具体看代码，代码详细注释，花点时间仔细看看能懂得。如果不懂，网上搜搜深度优先搜索讲解视频。黑窗口运行效果和代码#incl
·
1. 题目
数据结构课程，讲完栈，老师留下严蔚敏PPT上的作业，迷宫求解，如下：
2. 解题思路
1）采用递归的深度优先搜索，从出发点搜索至结束点
2）递归中自带“栈特性”，在进入当前递归函数相当于栈的push，退出当前递归函数相当于栈的pop，那么根据这个特性，实现搜索地图中返回上一个结点的功能。
具体看代码，代码详细注释，花点时间仔细看看能懂得。如果不懂，网上搜搜深度优先搜索讲解视频。
3. 黑窗口运行效果和代码
#include <iostream>
#include <stack>
#include <windows.h>
using namespace std;
// 地图值: 1是墙壁，0是通道，2是主角所在位置，3是出口 4是不能通过的标记
#define WALL 1
#define PASS 0
#define ZHUJUE 2
#define EXITS 3
#define NOPATH 4
// 全局变量
int m = 10, n = 10; // 行和列 默认为10
int map[100][100]; // 地图数组，先开大一点，根据m、n限定范围
int vis[100][100]; // 是否访问过，0是没访问，-1是访问过了
bool isFind = false; // 是否找到出口
stack<int(*)> pathStack;// 用STL模板的栈类记录路径
// 打印地图值
void PrintMap(int flag) {// 根据flag是否清除控制台内容
if (flag == 0) {
COORD position;
position.X = 0;
position.Y = 0;
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), position);
cout << "搜索地图中..............." << endl;
}
Sleep(250); // 休眠0.25秒，更新输出内容
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
{
if (map[i][j] == ZHUJUE) {// 主角当前所在位置
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 12);// 红色
cout << "☆";
continue;
}
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 0x07);// 白色字体
if (map[i][j] == WALL || map[i][j] == EXITS) { // 墙
cout << "■";
}
if (map[i][j] == PASS) { // 路
cout << " ";// 要2个空格
}
if (map[i][j] == NOPATH) { // 不能通过
cout << "×";
}
}
cout << endl;
}
cout << endl;
}
/*
思路：采用深度优先搜索
递归中自带“栈特性”，在进入当前递归函数相当于栈的push，退出当前递归函数相当于栈的pop
那么根据这个特性，实现搜索地图中返回上一个结点的功能。
*/
void DFS(int cury, int curx, int lasty, int lastx, int ysval) {// cury curx 表示当前点， lasty,lastx 表示上一个点，ysval表示上一个点的地图值
if (isFind) {// 找到了出口，递归栈都返回
return;
}
if (vis[cury][curx] == -1 || map[cury][curx] == 1 || cury >= m || cury < 0 || curx >= n || curx < 0) {// 递归返回条件:这个位置访问过，墙壁，越界，
return;
}
if (map[cury][curx] == EXITS) {// 递归退出条件，找到了出口
// cout << "找到了出口" << endl;
isFind = true;
return;
}
// 递归函数执行时，执行相当于栈push时的操作
pathStack.push(new int[2]{cury, curx});// 记录当前路径
vis[cury][curx] = -1; // 表示访问过当前点
int curysval = map[cury][curx]; // 保存当前的地图值
// 更新主角所在位置。
map[lasty][lastx] = ysval; // 上一个所在的位置变回地图值
map[cury][curx] = ZHUJUE; // 现在所在的位置为2，
PrintMap(0); // 递归函数执行时，当前的地图值
// 上下左右四个方向探索，并传入当前位置和当前的地图值（以便在下一个递归函数把当前主角所占的位置变回地图值）
DFS(cury, curx + 1, cury, curx, curysval);// 先向右边探索，为了符合PPT上的图展示效果，不过应该优先向下探索的。
DFS(cury + 1, curx, cury, curx, curysval);// 向下边探索
DFS(cury, curx - 1, cury, curx, curysval);// 向左边探索
DFS(cury - 1, curx, cury, curx, curysval);// 向上边探索
if (isFind) {// 找到了出口，现在的路径栈保存了正确的访问路径，退出即可，但是这个路径可能不是最优路径
return;
}
// 4个方向都走完了，无路可走，说明这个位置不能通过，需要返回上一个位置
// 递归函数结束时，相当于栈pop时的操作
// 需要把递归函数进入时改变的数值等操作回归原位
//vis[cury][curx] = 0; // 当前点没访问过，去掉没影响，但恢复为0可能可以找到最优路径
pathStack.pop(); // 舍去记录当前位置
map[cury][curx] = NOPATH; // 这个位置的值为不能通过
map[lasty][lastx] = ZHUJUE; // 上一个所在的位置为2
PrintMap(0); // 打印当前的地图值
}
// 根据栈保存的路径值，修改地图值
void UpdateMapToPath() {
while (!pathStack.empty()) {
int *pos = pathStack.top();
pathStack.pop();
map[*pos][*(pos + 1)] = 2;
}
}
int main() {
int val;
cout << "请输入地图行数和列数：" << endl;
cin >> m >> n;
cout << "请输入地图数据：" << endl;
// 1.根据输入初始化地图
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
{
cin >> val;
map[i][j] = val;
}
}
int endy = m - 2, endx = n - 1; // 出口列和行，列是x，y是行
int curx = 1, cury = 1; // 主角所在的开始行和列
map[endy][endx] = EXITS;// 给出口位置标记
system("cls");// 清空输入
// 2.深度优先搜索，找到路径
DFS(cury, curx, cury, curx, map[cury][curx]);
// 3.根据栈保存的信息，修改地图访问的路径
cout << "成功找到出口，访问出口路径如下:" << endl;
UpdateMapToPath();
PrintMap(1); // 最后打印访问过的路径图
}
/*
地图值
10 10
1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 1 0 1
1 0 0 1 0 0 0 1 0 1
1 0 0 0 0 1 1 0 0 1
1 0 1 1 1 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1
1 0 1 0 0 0 1 0 0 1
1 0 1 1 1 0 1 1 0 1
1 0 0 0 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1
11 10
1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 1 0 1
1 0 0 1 0 0 0 1 0 1
1 0 0 0 0 1 1 0 0 1
1 0 1 1 1 0 0 0 0 1
1 0 0 0 1 0 1 0 0 1
1 0 1 0 0 0 1 0 0 1
1 0 1 1 1 0 1 1 0 1
1 0 0 0 0 1 0 1 0 1
1 0 1 0 0 0 0 1 0 1
1 1 1 1 1 1 1 1 1 1
*/
4. 可视化地图效果和代码
完成黑窗口效果后，想使用可视化界面，于是使用了easyx图形库，很简单的将代码重构成和PPT一样的效果，代码变化不大。
要想运行这个代码，得安装easyx库，可以看这篇CSDN博客EASYX使用教程
#include <iostream>
#include <graphics.h> // 引用图形库头文件
#include <conio.h>
#include <stack>
#include <windows.h>
using namespace std;
// 地图值: 1是墙壁，0是通道，2~5是主角的方向（上下左右），6是出口
#define WALL 1
#define PASS 0
#define UP 2
#define DOWN 3
#define LEFT 4
#define RIGHT 5
#define EXITS 6
// 全局变量
int m = 10, n = 10; // 行和列 默认为10
int map[100][100]; // 地图数组，先开大一点，根据m、n限定范围
int vis[100][100]; // 是否访问过，0是没访问，-1是访问过了
bool isFind = false; // 是否找到出口
stack<int(*)> pathStack;// 用STL模板的栈类记录路径
// 加载图片
IMAGE imgs[10];
void LoadImags() {
loadimage(&imgs[0], L"lu.png", 80, 80);
loadimage(&imgs[1], L"qiang.png", 80, 80);
loadimage(&imgs[2], L"u.png", 80, 80);
loadimage(&imgs[3], L"d.png", 80, 80);
loadimage(&imgs[4], L"l.png", 80, 80);
loadimage(&imgs[5], L"r.png", 80, 80);
loadimage(&imgs[6], L"qiang.png", 80, 80);
}
// 绘制地图
void DrawMap() {
Sleep(300); // 休眠0.3秒，更新图
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
{
putimage(j * 80, i * 80, &imgs[map[i][j]]);
}
}
}
// 辅助函数，当前方向的对立方向
int GetAnotherDir(int dir) {
if (dir == 2) {
return 3;
}
if (dir == 3) {
return 2;
}
if (dir == 4) {
return 5;
}
if (dir == 5) {
return 4;
}
return dir;
}
/*
思路：采用深度优先搜索
递归中自带“栈特性”，在进入当前递归函数相当于栈的push，退出当前递归函数相当于栈的pop
那么根据这个特性，实现搜索地图中返回上一个结点的功能。
*/
void DFS(int cury, int curx, int dir, int lasty, int lastx, int ysval) {// cury curx 表示当前点，dir是当前位置的方向， lasty,lastx 表示上一个点，ysval表示上一个点的地图值
if (isFind) {// 找到了出口，递归栈都返回
return;
}
if (vis[cury][curx] == -1 || map[cury][curx] == 1 || cury >= m || cury < 0 || curx >= n || curx < 0) {// 递归返回条件:这个位置访问过，墙壁，越界，
return;
}
if (map[cury][curx] == EXITS) {// 递归退出条件，找到了出口
// cout << "找到了出口" << endl;
isFind = true;
return;
}
// 递归函数执行时，执行相当于栈push时的操作
pathStack.push(new int[3]{ cury, curx, dir });// 记录当前路径和方向
vis[cury][curx] = -1; // 表示访问过当前点
int curysval = map[cury][curx]; // 保存当前的地图值
// 更新主角所在位置。
map[lasty][lastx] = ysval; // 上一个所在的位置变回地图值
map[cury][curx] = dir; // 主角现在所在的位置 = 主角面向方向值
DrawMap(); // 递归函数执行时，当前的地图值
// 上下左右四个方向探索，并传入当前位置和当前的地图值（以便在下一个递归函数把当前主角所占的位置变回地图值）
DFS(cury + 1, curx, DOWN, cury, curx, curysval);// 先向下边探索，这里先往下搜索，对比一下先向右边探索
DFS(cury, curx + 1, RIGHT, cury, curx, curysval);// 向右边探索
DFS(cury, curx - 1, LEFT, cury, curx, curysval);// 向左边探索
DFS(cury - 1, curx, UP, cury, curx, curysval);// 向上边探索
if (isFind) {// 找到了出口，现在的路径栈保存了正确的访问路径，退出即可，但是这个路径可能不是最优路径
return;
}
// 4个方向都走完了，无路可走，需要返回上一个位置
// 递归函数结束时，相当于栈pop时的操作
// 需要把递归函数进入时改变的数值等操作回归原位
//vis[cury][curx] = 0; // 当前点没访问过，去掉没影响，但恢复为0可能可以找到最优路径
pathStack.pop(); // 舍去记录当前位置
map[cury][curx] = curysval; // 现在所在的位置变回一开始的地图值
map[lasty][lastx] = GetAnotherDir(dir); // 主角返回到上一个位置，上一个位置的方向，是当前对立的方向才能绘图正确
DrawMap(); // 绘制当前的地图值
}
// 根据栈保存的路径值，修改地图值
void UpdateMapToPath() {
while (!pathStack.empty()) {
int* pos = pathStack.top();
pathStack.pop();
map[*pos][*(pos + 1)] = *(pos + 2); // 变成主角当时的方向值
}
}
int main()
{
int val;
cout << "请输入地图行数和列数：" << endl;
cin >> m >> n;
cout << "请输入地图数据：" << endl;
// 1.根据输入初始化地图
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
{
cin >> val;
map[i][j] = val;
}
}
int endy = m - 2, endx = n - 1; // 出口列和行，列是x，y是行
int curx = 1, cury = 1; // 主角开始行和列
map[endy][endx] = EXITS; // 给出口位置标记
initgraph(n * 80, m * 80); // 创建绘图窗口，大小为 n * 80,m * 80 像素
LoadImags();
// 2.深度优先搜索，找到路径
DFS(cury, curx, DOWN, cury, curx, map[cury][curx]);
// 3.根据栈保存的信息，修改地图访问的路径
UpdateMapToPath();
DrawMap();
_getch(); // 按任意键继续
closegraph(); // 关闭绘图窗口
}
/*
地图值
10 10
1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 1 0 1
1 0 0 1 0 0 0 1 0 1
1 0 0 0 0 1 1 0 0 1
1 0 1 1 1 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1
1 0 1 0 0 0 1 0 0 1
1 0 1 1 1 0 1 1 0 1
1 0 0 0 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1
11 10
1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 1 0 1
1 0 0 1 0 0 0 1 0 1
1 0 0 0 0 1 1 0 0 1
1 0 1 1 1 0 0 0 0 1
1 0 0 0 1 0 1 0 0 1
1 0 1 0 0 0 1 0 0 1
1 0 1 1 1 0 1 1 0 1
1 0 0 0 0 1 0 1 0 1
1 0 1 0 0 0 0 1 0 1
1 1 1 1 1 1 1 1 1 1
*/
5.最后
你当我老师，你给我打几分。。。
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
9
0- 0
已为社区贡献2条内容
所有评论(0)