迷宫求解
一:迷宫求解是一个锻炼我们的算法求解能力的问题,它的实现方法有很多;今天我们就介绍其中的用栈求解的方法。
二:什么是栈:
大家应该都有往袋子里装东西的经历,在往袋子里装满东西之后,当我们去取的时候,总是先从最后放进去的东西的地方去取。也就是后进先出(FILO)。虽然栈的单向性用起来会没有链表那样可以在任意位置对数据进行操作,但是正因为如此栈也带来了很大的方便。
三:迷宫求解
现在我们要在下面的迷宫寻找一条可行的路径
1 1 1 1 1 1 1 1 1 1
1 0 0 1 1 0 0 0 0 1
1 0 0 0 1 0 1 0 0 1
1 0 1 0 0 0 1 1 0 1
1 0 1 0 0 0 1 1 1 1
1 0 1 1 1 0 1 1 1 1
1 0 1 1 1 0 1 1 1 1
1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1
首先我们需要在程序中表示上面的迷宫,该问题可以用数组实现
1:栈的定义
/************************************************************************/
/*自定义栈 */
/*通过自定义的简单栈以满足迷宫求解 */
/*功能:push() 将元素加入栈中 */
/* pop() 退栈;topValue() 获得栈顶元素 */
/* clear() 清除栈 length() 获得栈中元素个数*/
/************************************************************************/
#include <stack>
#include <iostream>
using namespace std;
template<typename Elem> class PathStack: public stack<Elem>
{
private:
int size;
int top;
Elem* listArray;
public:
PathStack(int sz = DefaultListSize){
size = sz;
top = 0;
listArray = new Elem[sz];
}
~PathStack(){ delete []listArray; }
void clear(){ top = 0; }
/****向栈中加入元素****/
bool push(const Elem& item);
/***********退栈**********/
Elem pop();
/********获得栈顶元素*******/
Elem topValue() const;
int length() const { return top; }
};
template<typename Elem>
bool PathStack<typename Elem>::push(const Elem& item){
if(top == size) return false;
listArray[top++] = item;
return true;
}
template<typename Elem>
Elem PathStack<typename Elem>::pop(){
Elem it;
if(top == 0) return it;
it = listArray[--top];
return it;
}
template<typename Elem>
Elem PathStack<typename Elem>::topValue() const{
Elem it;
if(top == 0) return it;
it = listArray[top - 1];
return it;
}
2:如何实现路径的寻找
1:设定寻找的方向,可以使用一个判断语句;判断起始位置周围哪个地方有路就将该位置的坐标加入到栈中,并将该位置标记(将改位置值改为2,既将走过的位置标记为2)
2:判断该位置周围是否还有路,若没有则退栈即退回到上一个位置;并将该位置做下另一个标记(将该位置值改为3,既将退栈位置值用3标记)
3:重复1,2步骤直到达到出口
路径寻找的类:
//迷宫求解的方法类
//功能:通过findPath() 方法实现对路径的查找
// 通过printPath()方法将路径打印出来
#include "PathStack.h"
#include <iostream>
using namespace std;
class MazeSolveMethod
{
private:
static int maze[10][10];//存放迷宫数据
PathStack<int> pathStack;//定义栈
public:
MazeSolveMethod():pathStack(100){
}
~MazeSolveMethod(){ }
void findPath(int startX,int startY);
void printPath() const;
};
int MazeSolveMethod::maze[10][10] = {
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,1,0,0,0,0,1},
{1,0,0,0,1,0,1,0,0,1},
{1,0,1,0,0,0,1,1,0,1},
{1,0,1,0,0,0,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,1,1,1,1,0,0,0,1,1},
{1,1,1,1,1,1,1,0,0,1},
{1,1,1,1,1,1,1,1,1,1},
};
void MazeSolveMethod::findPath(int startX,int startY){
int x = startX;
int y = startY;
pathStack.push(x);
pathStack.push(y);
maze[x][y] = 2;
cout<<"进入方法!"<<endl;
while(true){
if(maze[x-1][y] == 0){
pathStack.push(--x);
pathStack.push(y);
maze[x][y] = 2;
}else if(maze[x][y-1] == 0){
pathStack.push(x);
pathStack.push(--y);
maze[x][y] = 2;
}else if(maze[x][y+1] == 0){
pathStack.push(x);
pathStack.push(++y);
maze[x][y] = 2;
}else if(maze[x+1][y] == 0){
pathStack.push(++x);
pathStack.push(y);
maze[x][y] = 2;
}
if(maze[x-1][y] != 0 && maze[x][y+1] != 0 && maze[x+1][y] != 0 && maze[x][y-1] != 0){
if(x >= 8 && y >= 8){
break;
}else{
maze[x][y] = 3;
y = pathStack.pop();
x = pathStack.pop();
}
y = pathStack.topValue();
int temp = pathStack.pop();
x = pathStack.topValue();
pathStack.push(temp);
}
}
}
void MazeSolveMethod::printPath() const{
cout<<"printPath"<<endl;
for(int i=0; i<10; i++){
for(int j=0; j<10; j++){
if(maze[i][j] == 2)
cout<<'*'<<" ";
else if(maze[i][j] == 3)
cout<<0<<" ";
else
cout<<1<<" ";
}
cout<<endl;
}
}
主函数类
/************************************************************************/
/*迷宫求解----栈方法实现*/
//功能:通过对栈实现迷宫算法求解
//Author:Andrew
//Date :2012-10-20
/************************************************************************/
#include "MazeSolveMethod.h"
#include <iostream>
using std::cout;
using std::endl;
int main(){
MazeSolveMethod solve;
solve.findPath(1,1);
solve.printPath();
system("pause");
return 0;
}
将上面的代码运行后结果截图如下:
其中* 为路径
- 大小: 18.8 KB
分享到:
相关推荐
该程序采用了Python的smtplib模块和pyqt5模块,实现了自动登录QQ邮箱的功能,并且支持向其他QQ邮箱或如网易邮箱等其他类型的邮箱发送文本邮件和附带文件的邮件。
2024年全球胚胎移植玻璃化冷冻介质行业总体规模、主要企业国内外市场占有率及排名
多式联运 (1)
sklearn中决策树算法进行泰坦尼克号人员幸存预测 有包的导入、数据处理、特征提取、预测结果等
编译原理实验报告(1和2)(可运行)
数据库第一次满分上机报告
j2se6.chm.zip
ins爬虫on工具,能够批量爬取ins资源
库房检测APP.apk
系统主要分员工管理员两个角色 管理模块具体有商品管理,部门员工管理,进货管理,订单管理,换货管理,供应商管理,供应商管理,客户管理,公告通知管理等模块,而员工模块具体由商品管理,进货管理,订单管理,供应商管理,客户管理,换货订单管理,公告通知管理等模块组成。 仓库管理信息系统所涉及的主要数据包括商品管理、进货管理、订单管理、换货管理和供应商管理,客户管理,公告通知管理下面分别分析这些数据需求。 (1)商品管理 商品管理主要是管理商品分类信息以及管理商品信息。 (2)进货管理 进货管理主要员工可以登记进货信息,以及查看我的进货记录,而管理员可以添加进货信息以及对进货信息的管理。 (3)订单管理 订单管理主要是对订单的一个统计,员工对销售的订单进行登记,管理员可以管理员工们的订单销售。 (4)换货管理 换货管理主要员工可以登记换货信息,以及查看我的换货记录,而管理员可以添加换货信息以及对换货信息的管理。 (5)供应商管理 管理员可以管理对他们厂家的供应商,来达到可以很好及时的跟供应商进行沟通。 (6)客户管理 管理员可以管理客户。对客户进行维护。
没有word只有图片,打印图片打印出来发黑怎么办?如何像打印doc一样清楚。教你一招搞定
matlab 独立分量分析 fastica,icaplot,remmean,whiten,盲源分离,去均值,白化处理.zip
文档Python双指针算法模板和题目同向相向快速排序归并排序提取方式是百度网盘分享地址
向天歌【简约扁平化】大学生实习社会实践报告.ppt
GEK气化炉sw18可编辑设计图纸.7z
数据来源:中经数据库 数据范围:各个省份的区县财政收入即一般公共预算收入、税收收入 (一般财政收入即一般公共预算收入的完整度较高。税收收入一般50%的区县会有数据) 数据年度区间:2000-2023(具体看文件名上的年度区间) 珍贵数据,包含了各省所有的区、县、县级市哦,很难找到的哦
tetris.rar
100L化学槽罐sw18可编辑设计图纸.7z
自动驾驶-决策规划算法八:贝塞尔曲线(C++)