走迷宫!
2022/5/24 23:50:26
本文主要是介绍走迷宫!,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
自动化走迷宫
做maze题时不用自己在看花眼的maze里找路线了!!!
1.策略
为了能回溯,也就是没路走时可以往回走, 这里采用了栈存储之前的路线,maze则采用了vector二位数组存储。
那么简单地想,每一点位对四个方向进行检测,不断走下去,直到没路可走,便出栈往回走。这样会碰到什么问题呢? 由于进入一个点位的方向未知, 在试探四个方向时,可能会走回到上一个点位, 那就把该方向屏蔽,这样就需要给每个方向偏移打上一个标记位, 区分是否会回到上一个点位。
我们采用另一种办法, 即将走过的点位标记为障碍物, 从而避免了自发地走回去的可能性, 而当没路走时, 仍然可以通过栈回溯到之前的点位。
具体细节请看代码
2.code
先来栈代码
偏移结构和坐标结构也定义在这里,因为这个数据结构是按c风格写的,所以不太方便,只能把结构体定义在这里。
#include <stdio.h> #include <malloc.h> #include <stdbool.h> typedef struct coordinate ElementType; typedef struct SNode* PtrToSNode; //坐标 struct coordinate { int row; int col; }; //行动偏移, row表示行偏移, col表示列偏移 struct offsets { int row; int col; }; //初始定义 typedef struct SNode { ElementType* Data; int Top; int MaxSize; }* Stack; //创建一个栈空间 Stack CreateStack(int MaxSize) { Stack s = (Stack)malloc(sizeof(struct SNode)); s->Data = (ElementType*)malloc(MaxSize * sizeof(ElementType)); s->Top = -1; s->MaxSize = MaxSize; return s; } //判断栈是否满 bool Isfull(Stack s) { return s->Top == s->MaxSize - 1; } //判断栈是否空 bool IsEmpty(Stack s) { return s->Top == -1; } //压栈 bool Push(Stack s, ElementType element) { if(Isfull(s)) { printf("Stack is full!"); return false; } else { s->Data[++(s->Top)] = element; } return true; } //出栈 ElementType Pop(Stack s) { if(IsEmpty(s)) { printf("Stack is empty!"); return {0, 0}; } else { return s->Data[s->Top--]; } }
然后是主要的实现代码。
//走迷宫,哈哈 #include "stack.h" #include <iostream> #include <vector> using namespace std; int main() { cout << "请分别输入可行块、障碍块、入口、出口" << endl; char able, hinder, entry, exit; cin >> able >> hinder >> entry >> exit; //分别代表四种方块 getchar(); //读取这里的换行符 Stack s = CreateStack(0x80); //创建一个栈 struct offsets mov[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //偏移数组,0-3四个下标对应上下左右偏移 vector<char> Row1{hinder}; //新建一个vector容器用来储存第一行,以便于判断列数 //在第一列加了边界 char input; //输入缓冲 cout << "请输入迷宫矩阵, 以“!”表示迷宫输入结束。" << endl; while ('\n' != (input = getchar())) //一直读到换行符 { Row1.push_back(input); } Row1.push_back(hinder); int column_size = Row1.size(); //在末尾加边界,并计算长度 vector<vector<char>> maze{vector<char>(column_size, hinder), Row1}; //创建二位的数组, 初始化了前两行,第一行是边界 while (true) { cin >> input; if (input == '!') break; maze.push_back(vector<char>{hinder, input}); int num_row = maze.size() - 1; for (int i = 2; i <= column_size - 2; i++) { cin >> input; maze[num_row].push_back(input); } maze[num_row].push_back(hinder); } //重复读取直到!, 这里内层循环便于在首尾加边界 maze.push_back(vector<char>(column_size, hinder)); int row_size = maze.size(); //在最后加边界, 计算行数 struct coordinate cd_entry; for (int i = 0; i < row_size; i++) { for (int j = 0; j < column_size; j++) { if (maze[i][j] == entry) { cd_entry = {i, j}; break; } } } //检索, 找到入口点 /* 至此,初始化完毕, 开始走迷宫 */ struct coordinate next_cd, now_cd; //定义现在坐标、下一步坐标 int direction = 0, found = 0; //方向(偏移数组的下标), 是否找到出口的标记 vector<int> route{0}; //储存路线的vector容器 Push(s, cd_entry); //初始压栈, 便于待会给定入口坐标 maze[cd_entry.row][cd_entry.col] = hinder; //以下的策略是进入一个点,就将其标记为障碍物,从而杜绝了自发走回已过点位的可能性(靠出栈能往回走), 这里将入口点标记为障碍物 while (!IsEmpty(s) && !found) //栈空时表示前方无路,通过出栈一直回到了起点 { now_cd = Pop(s); //回到上一个点位,四个方向都不行时会回到这里。 route.pop_back(); //删除路线中刚刚记录的行动 direction = 0; //重置方向 //出发 while (direction < 4 && !found) { next_cd = {now_cd.row + mov[direction].row, now_cd.col + mov[direction].col}; if (maze[next_cd.row][next_cd.col] == exit) //如果是出口 { route.push_back(direction); found = 1; } else if (maze[next_cd.row][next_cd.col] == able) //如果下一个点可以走(没走过且不是障碍物) { route.push_back(direction); Push(s, now_cd); maze[next_cd.row][next_cd.col] = hinder; now_cd = next_cd; direction = 0; } else direction++; //换一个方向 } } cout << endl; if (found) { //终于出来了!呼...呼...呼......... for (int i = 0; i < route.size(); i++) { switch (route[i]) { case 0: cout << 'w'; break; case 1: cout << 's'; break; case 2: cout << 'a'; break; case 3: cout << 'd'; break; } } } else cout << "被困死了!!!" << endl; //寄 return 0; }
3.改进
学完栈的实现之后临时起意写的maze程序,有诸多问题,如stack是c风格,不清楚怎么在cpp文件中定义其元素, 所以最后是在h文件中定义了元素结构体。如果改成c++风格的stack,也就是使用模板类写这个stack,会好很多, 不过stl中其实直接就有stack的模板,直接调用也可以, 用模板的方便之处在于,可以直接创建存储不同元素的stack了, 而且函数都是封装好的,比每次还要传入栈这个参数方便。
再者,看过其他实现方式,也可以定义另外一个矩阵,以存储走过的点位,就不用每次走到某个点位把他变成hinder了(这可能更不方便了)
然后,这个程序要求最后输入一个!以提示输入完成, 如果在输入时直接指明行数和列数,代码会简单一些,我想尽可能简化使用程序的人的操作,也就是尽可能更智能,可以直接按输入的情况存储矩阵, 但又没想到更好的解决办法,便这么干了。
还有诸如代码风格等可能存在的其他问题,希望能得到大佬的指正。
这篇关于走迷宫!的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?