在我们学习数据结构的时候都曾经见过迷宫游戏，迷宫游戏的实现其实并不难，但是，我们在实现每一个算法的时候都应该想一想这个问题的每一个解。最近，博主已经开始重温数据结构啦，记得我们以前学习这里的时候，老师会用队列来实现迷宫最优解的寻找，氮素呢，博主就是这么可爱，博主就是想试试用栈来找一下。
创新互联专注于企业成都营销网站建设、网站重做改版、太平网站定制设计、自适应品牌网站建设、HTML5建站、商城建设、集团公司官网建设、成都外贸网站建设公司、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为太平等各大城市提供网站开发制作服务。在实现之前让我们先来复习一下栈的特点：first in last out
对于栈这种数据结构我们只能在栈顶对其操作，根据实际情况可将其实现成链式或者顺序结构。但是一般情况下我们都会实现成顺序结构，因为栈的特点导致了顺序结构管理方便，并且CPU缓存利用率更高。下面我们来简单的讲解一下迷宫小游戏
为了避免用户操作的不便性，我们选择将迷宫提前写好放在一个叫做"Maze.h"的文件中
*第一行的两个数字是迷宫的行和列
我们解决迷宫寻路问题的基本思想是回溯。回溯是什么意思呢？ 就是说，找不到就回退的思想。今天我们的程序要解决的问题是寻找最优解，所以，迷宫的每一条路我们都要去走一遍，这样，我们才能找到最短的那条路。
我们先来看一下程序是怎么写的（如果喷，请轻点
）
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include#include #include #include using namespace std; struct Pos { size_t _x; size_t _y; Pos(size_t x, size_t y) :_x(x), _y(y) {} }; stack min; bool IsValid(int *a, Pos cur, size_t R, size_t C) { if ((a[cur._x*C + cur._y] == 0) && (cur._x < R) && (cur._y < C)) return true; else return false; } void PrintMap(int *Map, size_t m, size_t n) { for (size_t i = 0; i < m; i++) { for (size_t j = 0; j < n; j++) { std::cout << Map[i*n + j] << " "; } std::cout << std::endl; } } void GetMaze(int *a,size_t Row,size_t Col,std::ifstream& fout) { size_t ch = 0; for (size_t i = 0; i < Row; i++) { for (size_t j = 0; j < Col;) { ch = fout.get()-'0'; if (ch == 0 || ch == 1) { a[i*Col + j] = ch; j++; } else continue; } } PrintMap(a, Row, Col); } bool Check(int *a,Pos entry,int R,int C) { Pos Up = entry; Pos Down = entry; Pos Left = entry; Pos Right = entry; Down._x++; Right._y++; Up._x--; Left._y--; if (IsValid(a, Down, R, C) || IsValid(a, Up, R, C) || IsValid(a, Left, R, C) || IsValid(a, Right, R, C)) return true; else return false; } bool GamePlay(int *a, Pos entry, size_t R, size_t C) { assert(a); stack s1; Pos man = entry; Pos next = man; Pos cur = entry; while ( 1 ) { if (!Check(a, man, R, C)) { cout << "最佳路径长度:"; cout << min.size() << endl; return true; } s1.push(man); while (!s1.empty()) { a[man._x*C + man._y] = 2; if (man._x == (R - 1) || man._y == (C - 1)) { cout << "Find&end" << endl; if ((s1.size() < min.size()) || min.size() == 0) min = s1; while (!s1.empty()) { cur = s1.top(); s1.pop(); if (Check(a, cur, R, C)) { man = cur; break; } } if (s1.empty()) { cout << "最佳路径长度:"; cout << min.size() << endl; return true; } } //********************************************下 next = man; next._x++; if (IsValid(a, next, R, C)) { s1.push(man); man = next; continue; } //********************************************右 next = man; next._y++; if (IsValid(a, next, R, C)) { s1.push(man); man = next; continue; } //********************************************左 next = man; next._y--; if (IsValid(a, next, R, C)) { s1.push(man); man = next; continue; } //********************************************上 next._x--; if (IsValid(a, next, R, C)) { s1.push(man); man = next; continue; } else { man = s1.top(); s1.pop(); } } man = entry; } } void GameTest() { //**********************从文件读入迷宫大小********************** ifstream fout("Maze.txt"); stack s1; int Row = 0; int Col = 0; char ch = fout.get(); while (ch != ' ') { int tmp = ch - '0'; s1.push(tmp); ch = fout.get(); } int c = 0; while (!s1.empty()) { Row += s1.top()*(int)pow(10, c); s1.pop(); c++; } ch = fout.get(); while (ch != ' '&&ch != '\n') { int tmp = ch - '0'; s1.push(tmp); ch = fout.get(); } c = 0; while (!s1.empty()) { Col += (int)s1.top()*(int)pow(10, c); s1.pop(); c++; } int *a = new int[Row*Col]; //******************************************************** Pos entry(0, 1); cout << endl << "*********** Map **********" << endl; GetMaze(a, Row, Col, fout); GamePlay(a, entry, Row, Col); cout << endl << "*********** Map **********" << endl; PrintMap(a, Row, Col); fout.close(); }
**记得在打开文件的时候做异常处理哦。博主在这里就不改了，小伙伴们自己看看
上面的代码呢，其实写的非常的不好，尤其是在代码复用的方面，不过，博主今天只是来举个栗子，今后会更加注意，你们也要注意哦，上面是个反面教材
（请理解一个看见自己代码想吐的我）
解法详解：用一个全局的栈结构来存储最优路径 min
用一个局部的站结构来存储当前一次得出的路径 s1
每一步都需要判断上下左右四个方向是否可走
***注意：每次判断时将next的值先赋成当前的位置再进行加减否则产生副作用
两层循环：里面一层即当前一次寻路完成
外面一层即再也无路可循时我们获得了最优解
**嗯，再看一眼仍然觉得这个代码看得我辣眼睛（捂脸）。
请围观群众不吝赐教哦~
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。